Vous êtes ici: Accueil » Mathématiques » Voronoï

Voronoï : un diagramme cellulaire

Qu'est ce qu'un diagramme de Voronoï  ?

Considérons un ensemble de points dans le plan, que l'on appelle germe. Chaque germe commence à grossir à la même vitesse, en définissant une région circulaire. Quand deux régions se rencontrent, une frontière linéaire se forme, le long de la médiatrice des deux germes associés. Lorsque la croissance des régions n'est plus possible, on obtient une partition du plan, où chaque zone est définie comme l'ensemble des points les plus proches d'un germe.

Exemple de diagramme de Voronoï

Ce genre de figure est appelé diagramme de Voronoï, du nom du mathématicien français qui l'a étudié au début du XXème siècle. Elle peut être utilisée pour modéliser des réseaux de cellules végétales, en mécanique ou encore dans les télécommunications. Vous pouvez essayer de vous familiariser avec via cette applet en ligne.


Partition de Delaunay

Une autre possibilité est d'afficher les liens entre les régions voisines. En traçant un segment entre un germe et les germes des régions voisines, on obtient une triangulation de Delaunay. Cette structure est très utile en mécanique, car c'est celle qui permet de mailler les objets de la manière la plus efficace, en minimisant les carrés des aires des triangles.

Théorie des graphes

Du point de vue de la théorie des graphes, le diagramme de Voronoï est le dual de la partition de Delaunay. C'est à dire que que l'on passe de l'un à l'autre très facilement, et qu'ils représentent la même chose. C'est la raison pour laquelle ces deux problèmes sont très souvent associés. Tous les deux sont des graphes planaires : on peut les dessiner sur un surface plane sans qu'aucuns de leurs arcs ne se croisent.

Téléchargement

Vous pouvez récuperer l'applet pour l'utiliser chez vous. Vous pouvez aussi télécharger les sources (en Java) pour étudier l'algorithme.

Liens

Si ces quelques lignes sur les graphes de Voronoï vous ont intéressé, je vous conseille les liens suivants :



Page précédente : Liens
Page suivante : Euclide