diagramme de Voronoï

Imaginez trois fontaines sur une place. Pour savoir laquelle est la plus proche de chaque endroit, on colorie ensemble tous les points qui choisissent la même fontaine. Chaque fontaine devient un germe, et sa zone est une cellule de Voronoï. Une frontière apparaît là où deux fontaines sont à la même distance. À l’intérieur d’une cellule, son germe reste au moins aussi proche que tous les autres.

Dans un espace muni d’une distance, on choisit des points appelés germes. Pour un ensemble fini de germes distincts, la cellule associée au germe s_i rassemble les points x dont la distance à s_i est inférieure ou égale à la distance à chaque autre germe s_j.

Avec la distance euclidienne et des germes ponctuels, une frontière commune suit une partie de la médiatrice de deux germes. Dans le plan, chaque cellule est alors l’intersection de demi-plans : elle est convexe, mais elle peut être non bornée. Les cellules couvrent le plan et leurs intérieurs ne se chevauchent pas ; une frontière peut appartenir à plusieurs cellules à cause du signe « inférieur ou égal ». La même définition vaut en dimension n. Voronoï a étudié ce cadre général, après des travaux de Dirichlet en dimensions deux et trois sur les formes quadratiques.

Sur une carte ou une figure, cherchez d’abord des points isolés, puis un réseau de lignes qui partage tout le support en zones jointives. Chaque zone contient généralement un germe. Ses côtés sont rectilignes dans le cas euclidien de germes ponctuels, et plusieurs côtés peuvent se rejoindre en un sommet. La couleur aide parfois à distinguer les cellules, mais elle ne les définit pas. Le support indique surtout, pour chaque position, quel germe est le plus proche selon la distance choisie.

La grandeur à lire est la distance au germe, mesurée dans le même repère pour tous les germes.

1. Choisissez un point du support.
2. Comparez sa distance à chaque germe.
3. Attribuez-le au germe qui donne la plus petite valeur.
4. En cas d’égalité, placez-le sur une frontière commune.

Dans un dessin euclidien, l’œil peut croire qu’un point appartient à la cellule dont le germe semble le plus proche horizontalement. La distance dépend pourtant des deux coordonnées. Le bon réflexe consiste à comparer les distances complètes, ou leurs carrés, qui donnent le même classement sans calculer de racines carrées. Une autre distance peut produire un autre découpage.

Dans un repère orthonormé, prenons trois germes : A(1 ; 1), B(5 ; 1) et C(3 ; 5). Nous voulons construire leurs cellules et décider à quel germe rattacher le point P(2 ; 2).

1. A et B ont la même ordonnée. Leur médiatrice est donc la droite x = 3.

2. L’égalité des distances à A et C donne x + 2y = 8. Pour B et C, elle donne x − 2y + 2 = 0.

3. Les trois médiatrices se rencontrent en O(3 ; 2,5). Les portions utiles de ces droites forment les trois frontières représentées dans le cadre.

4. Pour P, les carrés des distances valent PA² = 2, PB² = 10 et PC² = 10. P appartient donc à la cellule de A.

Le contrôle est refaisable : O est à 2,5 unités de A, de B et de C. Il est donc équidistant des trois germes, comme doit l’être ce sommet du diagramme.

En urbanisme, des équipements ponctuels peuvent servir de germes : le diagramme attribue chaque position à l’équipement le plus proche. Si le temps de trajet compte davantage que la distance à vol d’oiseau, il faut préférer un découpage fondé sur le réseau de rues.

En météorologie ou en géophysique, des stations de mesure peuvent délimiter des zones de proximité. Cette partition convient pour une attribution au voisin le plus proche ; une interpolation est préférable lorsque l’on veut une valeur qui varie progressivement entre stations.

En biologie et en informatique graphique, le même principe sert à étudier un voisinage ou à produire une partition spatiale. Le choix des germes et de la distance doit correspondre au phénomène observé. John Snow en fit un usage précoce en 1854 pour analyser la propagation d’une épidémie de choléra.

Avec le complexe de Delaunay. Le diagramme de Voronoï découpe l’espace en cellules de proximité. Le graphe de Delaunay relie des germes dont les cellules de Voronoï partagent une frontière ; en position générale, ses faces forment une triangulation duale du diagramme. En cas de germes cocirculaires, plusieurs triangulations peuvent convenir. Dans l’exemple A, B, C, le diagramme montre trois cellules, tandis que le dual relie les trois germes en un triangle.

Avec un pavage régulier. Un pavage régulier impose des formes répétées choisies à l’avance. Un diagramme de Voronoï est déterminé par les germes et la distance : déplacer seulement C dans l’exemple modifie les frontières, sans qu’un motif régulier soit requis.

Égalité sur une frontière. Un point situé à égale distance de deux germes appartient aux deux cellules avec la définition par « inférieur ou égal ». Pour obtenir des zones disjointes en informatique, il faut ajouter une règle explicite de départage.

Sommet dégénéré. Si quatre germes ou davantage sont sur un même cercle sans autre germe à l’intérieur, quatre cellules ou davantage peuvent se rencontrer au même sommet. La rencontre de trois cellules est donc fréquente, mais elle n’est pas universelle.

Germes répétés. Deux germes aux mêmes coordonnées sont indiscernables par la distance. Il faut les fusionner ou fixer une convention avant d’attribuer les points.

Cadre trompeur. Une cellule coupée par le bord d’une carte paraît bornée, alors que sa version dans le plan entier peut se prolonger à l’infini. Il faut distinguer le diagramme mathématique de sa fenêtre d’affichage. Avec des poids, des obstacles ou une autre métrique, les frontières ne sont plus nécessairement les médiatrices droites du cas euclidien non pondéré.

Le dual géométrique relie deux germes lorsque leurs cellules de Voronoï partagent une frontière. Cette relation conduit à la triangulation de Delaunay et ouvre sur les algorithmes qui construisent, interrogent et mettent à jour ces structures.

Les enjeux de la géométrie algorithmique présente le cadre algorithmique dans lequel les partitions spatiales et leurs structures duales deviennent des outils de calcul.