Diagrammes de Voronoï

Les diagrammes de Voronoï permettent de découper le plan (ou une région de l’espace) en zones en fonction de la distance à un ensemble donné de points. Ils sont utilisés en biologie pour modéliser la croissance cellulaire, en épidémiologie pour identifier les sources d’infection et en urbanisme pour déterminer les zones de chalandise des écoles, des hôpitaux ou des bureaux de poste.
L’idée est simple : étant donné un ensemble de points (appelés sites), on partage la carte de sorte que chaque point d’une région soit plus proche de son site associé que de tout autre site.

Considérons un ensemble de points appelés sites.

• Pour chaque site, sa région (ou cellule) est constituée de tous les points plus proches de ce site que de tout autre site.
• Une arête (ou frontière) est un segment de droite (ou une demi-droite) constitué de points équidistants de deux sites.
• Un sommet (ou nœud) est un point équidistant d’au moins trois sites. C’est le point d’intersection des arêtes.

Avec trois sites (A, B et C), le plan est divisé en trois régions de Voronoï colorées.

• La région rouge contient tous les points qui sont les plus proches de A.
• La région bleue contient tous les points qui sont les plus proches de B.
• La région verte contient tous les points qui sont les plus proches de C.

Les frontières (arêtes) se rejoignent en un sommet V qui est équidistant des trois sites.

Pour construire un diagramme pour 2 sites, tracer la médiatrice du segment reliant les deux sites. Cette droite est la frontière entre leurs deux régions de Voronoï.

Pour construire un diagramme de Voronoï pour 3 sites~:

1. Tracer le triangle reliant les trois sites (en pointillés pour plus de clarté).
2. Tracer la médiatrice de chaque côté du triangle.
3. Ces trois médiatrices se coupent en un unique point. Ce point est le seul sommet du diagramme de Voronoï et est équidistant des trois sites.
4. Les arêtes du diagramme de Voronoï sont les trois demi-droites qui partent de ce sommet et s’étendent à l’infini le long de chaque médiatrice, dans la direction qui s’éloigne du triangle.

Le sommet représente le centre du cercle circonscrit au triangle \(ABC\). Il est équidistant de \(A\), \(B\) et \(C\).

Pour ajouter un nouveau site \(D\) à un diagramme existant :

1. Localiser la région de Voronoï existante qui contient \(D\) (c’est-à-dire la région du site actuellement le plus proche de \(D\)).
2. Tracer la médiatrice entre \(D\) et le site propriétaire de cette région.
3. Continuer à tracer les médiatrices entre \(D\) et les sites voisins jusqu’à ce que la cellule polygonale de \(D\) soit fermée.
4. Supprimer les anciennes arêtes qui se trouvent maintenant à l’intérieur de la nouvelle région.

Commençons par le diagramme de Voronoï pour \(A\), \(B\) et \(C\). Ajoutons un nouveau site \(D\).

1. Le site \(D\) se trouve dans la région de A. Nous traçons la médiatrice entre \(D\) et \(A\).
2. Un nouveau sommet \(V\) (en \(V_2\)) est ajouté. Ce sommet est équidistant de A, B et D. Nous devons donc tracer la médiatrice entre \(D\) et \(B\), en partant de \(V\) comme indiqué. Cette droite ne rencontre aucune autre arête existante, donc aucun nouveau sommet n’est créé. Cela nous indique que la construction de la cellule de \(D\) est terminée.
3. Enfin, nous supprimons la partie de l’arête entre \(A\) et \(B\) qui se trouve maintenant dans la cellule du site \(D\).

Étant donné un ensemble de valeurs de données associées aux sites, la valeur de tout point du plan peut être estimée en prenant la valeur du site dont la région de Voronoï contient ce point. On parle alors d’interpolation du plus proche voisin.

Une ville possède 3 bureaux de poste aux coordonnées \(A(1,1)\), \(B(5,1)\) et \(C(3,4)\).
Vous habitez en \(P(2,2)\). Quel bureau de poste vous dessert ?

• Distance \(PA = \sqrt{(2-1)^2 + (2-1)^2} = \sqrt{1+1} = \sqrt{2} \approx 1{,}41\).
• Distance \(PB = \sqrt{(2-5)^2 + (2-1)^2} = \sqrt{9+1} = \sqrt{10} \approx 3{,}16\).
• Distance \(PC = \sqrt{(2-3)^2 + (2-4)^2} = \sqrt{1+4} = \sqrt{5} \approx 2{,}24\).

Puisque \(PA\) est la plus petite distance, le point \(P\) se trouve dans la région de Voronoï de \(A\). Vous êtes desservi par le bureau de poste \(A\).

Une application classique consiste à trouver l’emplacement d’une ``décharge toxique'' (ou d’une usine bruyante). Le but est de trouver un emplacement à l’intérieur d’une limite donnée qui soit aussi éloigné que possible de toute habitation existante (les sites).

Le point situé à l’intérieur de l’enveloppe convexe des sites qui est le plus éloigné de tout site se trouve toujours à un sommet du diagramme de Voronoï.
Ce point est le centre du plus grand cercle vide que l’on peut tracer sans contenir aucun site.

Trois villes sont situées en \(A(0,0)\), \(B(4,0)\) et \(C(0,4)\). Nous voulons construire une déchetterie aussi loin que possible des trois villes.

1. Le segment \(AB\) est situé sur la droite \(y=0\) et a pour milieu \((2,0)\) ; sa médiatrice est donc la droite \(x=2\).
2. Le segment \(AC\) est situé sur la droite \(x=0\) et a pour milieu \((0,2)\) ; sa médiatrice est donc la droite \(y=2\).
3. L’intersection (sommet) est \(V(2,2)\).
4. Distance de \(V\) à \(A\) : \(\sqrt{(2-0)^2 + (2-0)^2} = \sqrt{8} \approx 2{,}83\).

Le point le plus éloigné des trois villes (à l’intérieur de leur enveloppe convexe) est \(V(2,2)\).