Diagramme de Voronoï

On peut faire remonter l’usage informel des diagrammes de Voronoï jusqu'à Descartes en 1644 dans Principia philosophiae comme illustration de phénomène astronomique [1]. Dirichlet a utilisé des diagrammes de Voronoï en dimension 2 ou 3 dans son étude des formes quadratiques en 1850 (Dirichlet 1850).

En 1854, le médecin britannique John Snow a utilisé le diagramme de Voronoï pour montrer que la majorité des personnes mortes dans l’épidémie de choléra de Soho se trouvaient dans la cellule de la pompe à eau de Broad Street, donc qu'ils vivaient plus près de cette pompe que de n’importe quelle autre pompe[2]. Il a ainsi démontré que le foyer de l'infection était cette pompe.

Les diagrammes de Voronoï portent le nom du mathématicien russe Georgy Fedoseevich Voronoï (ou Voronoy) qui a défini et étudié le cas général en dimension n en 1908[3] - [4]. Les diagrammes de Voronoï qui sont utilisés en géophysique et en météorologie pour analyser des données de distributions spatiales (comme les mesures de chutes de pluie) sont appelés polygones de Thiessen du nom du météorologiste américain Alfred H. Thiessen (en).

On se place dans le plan affine ${\displaystyle \mathbb {R} ^{2}}$. Soit S un ensemble fini de n points du plan ; les éléments de S sont appelés centres, sites ou encore germes.

On appelle région de Voronoï — ou cellule de Voronoï — associée à un élément p de S, l’ensemble des points qui sont plus proches de p que de tout autre point de S :

${\displaystyle \mathrm {Vor_{S}} (p)=\{x\in \mathbb {R} ^{2}\ /\ \forall q\in \mathrm {S} \ \|x-p\|\leq \|x-q\|\}}$

où ||x – p|| désigne la distance entre x et p.

Si l'on appelle H(p, q) le demi-plan contenant p délimité par la médiatrice du segment [pq], on a

${\displaystyle \mathrm {H} (p,q)=\{x\in \mathbb {R} ^{2}\ /\ \|x-p\|\leq \|x-q\|\}}$

${\displaystyle \mathrm {Vor_{S}} (p)=\bigcap _{q\in \mathrm {S} \backslash \{p\}}\mathrm {H} (p,q)}$

En dimension 2, il est facile de tracer ces partitions. On se base sur le fait que la frontière entre les cellules de Voronoï de deux germes distincts se situe forcément sur la médiatrice qui sépare ces deux germes. En effet, les points de cette médiatrice sont équidistants des deux germes donc on ne peut pas affirmer qu’ils se situent dans l'une ou l'autre cellule de Voronoi. Pour un ensemble de germes, le diagramme de Voronoï se construit donc en déterminant les médiatrices de chaque couple de germes. Un point d'une médiatrice appartient alors à une frontière de Voronoï s'il est équidistant d'au moins deux germes et qu'il n'existe pas de distance plus faible entre ce point et un autre germe de l'ensemble.

On peut généraliser la notion à un espace euclidien E muni de la distance euclidienne d. Soit S un ensemble fini de n points de E. La définition devient :

${\displaystyle \mathrm {Vor_{S}} (p)=\{x\in \mathrm {E} \ /\ \forall q\in \mathrm {S} \ \mathrm {d} (x,p)\leq \mathrm {d} (x,q)\}}$

Pour deux points a et b de S, l’ensemble Π(a , b) des points équidistants de a et b est un hyperplan affine (un sous-espace affine de co-dimension 1). Cet hyperplan est la frontière entre l’ensemble des points plus proches de a que de b, et l’ensemble des points plus proches de b que de a.

${\displaystyle \Pi (p,q)=\{x\in \mathrm {E} \ /\ \mathrm {d} (x,p)=\mathrm {d} (x,q)\}}$

On note H(a, b) le demi espace délimité par cet hyperplan contenant a, il contient alors tous les points plus proches de a que de b. La région de Voronoï associée à a est alors l’intersection des H(a, b) où b parcourt S\{a}.

${\displaystyle \mathrm {H} (p,q)=\{x\in \mathrm {E} \ /\ \mathrm {d} (x,p)\leq \mathrm {d} (x,q)\}}$

${\displaystyle \mathrm {Vor_{S}} (p)=\bigcap _{q\in \mathrm {S} \backslash \{p\}}\mathrm {H} (p,q)}$

Pour résoudre certains problèmes, Shamos[5] introduit la notion de diagramme de Voronoï d'un ensemble de points A (sous-ensemble de S), V(A), défini par :

${\displaystyle \mathrm {V} (\mathrm {A} )=\left\{x\in \mathrm {E} /\ \forall p\in \mathrm {A} ,\forall q\in \mathrm {S} \setminus \mathrm {A} ,\mathrm {d} (x,p)<\mathrm {d} (x,q)\right\}}$

Ainsi, V(A) est l'ensemble des points qui sont plus proches de chaque point de A que de n'importe quel point n'étant pas dans A.

Si l'on appelle H(i, j) le demi-plan délimité par la médiatrice du segment [ij] et contenant i, alors on a :

${\displaystyle \mathrm {V} (\mathrm {A} )=\bigcap _{i\in \mathrm {A} ,j\in \mathrm {S} \setminus \mathrm {A} }\mathrm {H} (i,j)}$

Les régions de Voronoï généralisées sont donc convexes, mais elles peuvent être vides. Shamos définit par la suite les diagrammes de Voronoï d'ordre k (1 ≤ k < card(S)) par la réunion des cellules de Voronoï généralisées formées par tous les sous-ensembles de k points :

${\displaystyle \mathrm {V} _{k}(\mathrm {S} )=\bigcup _{\mathrm {A} \subset \mathrm {S} ,\mathrm {card} (\mathrm {A} )=k}\mathrm {V} (\mathrm {A} )}$.

Les régions V(A) forment une partition de V_k(S).

Il définit également le « diagramme de Voronoï des points les plus éloignés » (farthest-point Voronoi diagram). Ce diagramme est construit en inversant le sens de l'inégalité

${\displaystyle {\overline {\mathrm {Vor} }}_{\mathrm {S} }(p)=\left\{x\in \mathrm {E} \ /\ \forall q\in \mathrm {S} \ \mathrm {d} (x,p)\geq \mathrm {d} (x,q)\right\}}$

Le point p ne se trouve évidemment pas dans la cellule Vor_S(p), mais à l'opposé par rapport au « centre » de l'ensemble : le point p est le point de S le plus éloigné de Vor_S(p).

Le diagramme des points les plus éloignés est entièrement déterminé par l'enveloppe convexe de S. Il ne contient pas de cellule fermée.

Ainsi, l'ensemble des points les plus éloignés d'un point p est l'ensemble des points qui sont plus proches des autres points de S :

${\displaystyle {\overline {\mathrm {Vor} }}_{\mathrm {S} }(p)=\bigcup _{q\in \complement _{\mathrm {S} }(\{p\})}\mathrm {Vor_{S}} (q)}$

donc le diagramme des points les plus éloignés est identique à V_{n – 1}(S), n = card(S).

Les régions de Voronoï sont des polytopes convexes en tant qu’intersection de demi espaces[alpha 1]. L’ensemble de tels polygones partitionne E, et est la partition de Voronoï correspondant à l’ensemble S.

Une autre propriété est que les deux points les plus rapprochés sont dans des cellules adjacentes.

Superposition d’un diagramme de Voronoï (en rouge) et de sa triangulation de Delaunay (en noir).

Le diagramme de Voronoï d’un ensemble discret S de points est le graphe dual de la triangulation de Delaunay associée à S.

Graphiquement, on représente en général les parois des cellules, c'est-à-dire les points qui sont à égale distance d'au moins deux centres, et les centres associés aux cellules. On représente parfois la cellule par un aplat de couleur, avec ou sans paroi, avec une couleur différente entre chaque cellule (voir Théorème des quatre couleurs).

D'un point de vue analytique, une cellule étant une intersection de demi-plans, elle peut être représentée comme le système d'équation de ces demi-plans (voir Géométrie analytique > Demi-plan) :

${\displaystyle \left\{{\begin{matrix}a_{1}x+b_{1}y\geqslant c_{1}\\a_{2}x+b_{2}y\geqslant c_{2}\\\cdots \end{matrix}}\right.}$

Pour représenter informatiquement un diagramme de Voronoï, John Burkardt[6] a proposé d'utiliser un fichier avec quatre types d'enregistrement :

• s x y : point de l'ensemble S, de coordonnées (x, y) ;
• v x y : sommet (vertex) d'un polygone de Voronoï, de coordonnées (x, y) ;
• l a b c : droite (portant une arête d'un polygone), d'équation ax + by = c ;
• e l v1 v2 : arête d'un polygone, décrit par l'indice l de sa droite porteur et les indices v₁ et v₂ des sommets qui sont ses extrémités ; si un indice est égal à –1, cela signifie que le sommet est « à l'infini » (demi-droite, ou droite si les deux sommets sont à –1).

Les diagrammes de Voronoï sont utilisés, ou réinventés sous de nombreux noms, dans différents domaines. Ils interviennent souvent lorsque l'on cherche à partitionner l'espace en zones d'influence. Quelques exemples :