LES DIAGRAMMES DE VERONOÏ

En géométrie, les diagrammes de Veronoï ( mathématicien russe Georgi Fedoseevich Voronoï, 1868 - 1908) sont des découpages d'un plan en secteurs polygonaux selon des règles décrites plus bas.

Ces découpages peuvent être appliqués à des espaces de dimension trois, voire n. Nous nous limitons ici à la géométrie plane en deux dimensions. Ces découpages ont des applications innombrables et ont fait l'objet, sous des noms divers, d'études avancées.

Exemple de diagramme de Veronoï

Imaginons un plan parsemé de n points que l'on appelle généralement des "germes". Un diagramme de Veronoï divise ce plan en secteurs polygonaux qui sont, en quelque sorte, les zones d'influence de ces germes. Plus précisément : à l'intérieur d'un de ces polygones aucun point n'est plus proche d'un autre germe que de celui qui est constitutif du polygone concerné. Sur la figure qui précède, considérons par exemple l'hexagone irrégulier, proche du centre de la figure, de couleur vert clair. Le point noir qui y figure est le germe constitutif. Aucun des points de couleur vert clair n'est plus proche d'un autre germe que de celui que nous avons mentionné.

La construction d'un diagramme de Veronoï est simple (mais laborieuse manuellement si le nombre de germes est grand). Le principe est de tracer, à partir de chacun des germes la médiatrice du segment qu'il forme avec chacun des autres germes les plus proches. La médiatrice est en effet l'ensemble des points qui sont à égale distance de deux points donnés. Les frontières des différents secteurs seront donc constituées par des tronçons de ces médiatrices.