Une subdivision de l’espace en régions (cellules) autour d’un ensemble de sites telle que chaque cellule contient tous les points plus proches de son site que de tout autre, produisant une tessellation utilisée pour l’analyse de proximité et les recherches du plus proche voisin.

Principe

La cellule de Voronoï d’un site est l’intersection des demi-espaces déterminés par les médiatrices perpendiculaires entre ce site et chaque autre ; l’ensemble des cellules recouvre le domaine par des régions convexes (en contexte euclidien) dont l’adjacence encode les relations de plus proche voisin.

Démonstration

Pour des sites S = {s1,s2,...,sn} dans le plan, la cellule de si est {x | dist(x,si) ≤ dist(x,sj) pour tout j} ; par exemple, construire les médiatrices perpendiculaires entre sites adjacents donne des cellules polygonales dont les sommets sont des centres circonscrits de triangles de Delaunay.

Mauvaise application

Employer des diagrammes de Voronoï avec une métrique inappropriée sans adapter la construction des médiatrices ou appliquer des propriétés euclidiennes standard (convexité, médiatrices droites) à des contextes non euclidiens peut produire des cellules incorrectes et des informations de proximité trompeuses.

Conséquence

Les diagrammes de Voronoï fournissent un index spatial canonique pour la recherche du plus proche voisin, les régions d’influence et le clustering spatial ; leur dual, la triangulation de Delaunay, soutient la génération de maillages et les requêtes géométriques efficaces.

Inversion

Inverser la perspective donne la triangulation de Delaunay, qui relie les sites en simplices dont les centres circonscrits forment les sommets de Voronoï ; cette inversion déplace l’accent de la propriété de région vers la connectivité simpliciale.

Limite

Défini pour des sites discrets dans des espaces métriques où sont bien définis distances et médiatrices ; en euclidéen les cellules sont des polytopes convexes, tandis que dans des métriques pondérées, anisotropes ou non euclidiennes les cellules peuvent être non convexes ou de structure plus complexe.

Tension sémantique

Les partitions de Voronoï sont parfois confondues avec des clusters de plus proches voisins ou des régions basées sur la densité ; contrairement au clustering probabiliste, les cellules de Voronoï sont des partitions déterministes induites par la métrique et n’intègrent pas la densité des données ni un lissage statistique sans extension.

Synthèse

Un diagramme de Voronoï est la partition de l’espace induite par la métrique en régions appartenant à chaque site obtenue par l’intersection de demi‑espaces issus des médiatrices pair‑à‑pair ; ses cellules convexes et sa dualité avec la triangulation de Delaunay en font une structure fondamentale pour la proximité, l’indexation spatiale et les algorithmes géométriques.