Diagramme de Voronoï

Un diagramme de Voronoï partage le plan entre un ensemble de points appelés sites : chaque site reçoit la région des points qui sont au moins aussi proches de lui que de tout autre site. L’image est une fenêtre sur le plan ; l’ombrage à l’intérieur d’une région sert seulement à la rendre lisible. La sonde bleue est le centre d’un cercle vide qui atteint le site le plus proche. Ici, tu peux déplacer les sites et voir les régions de leurs voisins changer, faire grandir chaque région depuis son site, afficher la triangulation de Delaunay et répartir les sites plus régulièrement pour tendre vers un nid d’abeilles.

Les points au moins aussi proches d’un site $p$ que d’un autre site $q$ forment un demi-plan délimité par la médiatrice de $pq$. La région de $p$ est l’intersection de ces demi-plans, un pour chaque autre site : elle est donc convexe. Seules certaines médiatrices deviennent des arêtes. Les sites dont les régions partagent une arête avec celle de $p$ sont ses voisins ; les autres demi-plans contiennent déjà toute la région. Le cadre ne fait que délimiter la fenêtre. Une région s’étend à l’infini si et seulement si son site appartient au bord de l’enveloppe convexe de tous les sites.

Là où trois régions ou plus se rencontrent, le sommet est à égale distance de leurs sites : c’est donc le centre d’un cercle passant par eux. L’intérieur de ce cercle ne contient aucun site. Sinon, ce site serait plus proche du sommet, et le sommet appartiendrait à sa région. En général, exactement trois régions se rencontrent à un sommet. Il y en a quatre lorsque exactement quatre sites sont sur un même cercle vide, comme sur une grille carrée, ce qui n’arrive presque jamais avec des sites placés au hasard.

Croître fait grandir un disque à la même vitesse depuis chaque site. Chaque point est atteint d’abord par son site le plus proche : les fronts se rencontrent donc exactement sur les arêtes. La petite vue montre la même croissance de côté. Au-dessus de chaque point, elle place une hauteur égale à la distance au site le plus proche : la plus basse des hauteurs des cônes $z = |x - s|$ dressés sur les sites. Les crêtes sont les arêtes, et la croissance est une montée des eaux. Le dernier endroit inondé est le point le plus haut du paysage dans le cadre, centre du plus grand cercle vide dont le centre est dans le cadre.

Triangulation relie deux sites dès que leurs régions partagent une arête et ajoute des diagonales en pointillé lorsque quatre sites ou plus partagent un cercle vide, comme sur une grille carrée. À moins que tous les sites soient alignés, on obtient la triangulation de Delaunay. Le cercle circonscrit de chaque triangle est le cercle vide autour d’un sommet du diagramme.

Uniformiser déplace chaque site au centre de gravité de sa région découpée par le cadre, puis recalcule les régions, tour après tour. C’est l’algorithme de Lloyd. Le petit graphique trace la distance quadratique moyenne d’un point du cadre au site le plus proche, divisée par l’aire du cadre par site. Aucun tour ne peut augmenter cette valeur. À sites fixes, les régions du site le plus proche la minimisent ; à régions fixes, ce sont les centres de gravité. La ligne du nid d’abeilles est une borne inférieure : la valeur pour des hexagones réguliers égaux dont les sites sont au centre. En partant de sites dispersés, le processus s’arrête dans un état stable voisin, pas dans un nid d’abeilles parfait. Il reste généralement des pentagones et des heptagones côte à côte, comme des dislocations dans un cristal.

Le diagramme porte le nom de Gueorgui Voronoï, qui a étudié ces découpages en dimension quelconque en 1908. La triangulation porte celui de Boris Delaunay, qui l’a décrite en 1934.