Télécharger une version imprimable au format pdf

Soit S un ensemble de points du plan, appelés générateurs. La cellule de Voronoï d'un générateur p est la région du plan contenant les points plus proches de p que de n'importe quel autre générateur.

Diagramme de Voronoi.

Le diagramme de Voronoï de S est la réunion des cellules de voronoï pour tous les points de S. Il définit ainsi une partition naturelle du plan (ou d'un espace en dimension arbitraire), et ses propriétés mathématiques en ont fait une structure géométrique essentielle pour de nombreuses applications algorithmiques.

Un diagramme de Voronoï centré appartient à une classe particulère de diagrammes de Voronoï. Soit un domaine borné et une fonction de densité définie sur ce domaine, un diagramme de Voronoï est centroidal lorsque chaque générateur coincide avec le centre de masse de sa région de Voronoï. Les propriétés de cette structure sont telles qu'on la retrouve dans les configurations optimales d'applications très diverses comme l'analyse numérique, la quantification vectorielle, la répartition optimale de ressources, la simulation de croissance de cellules, etc. Ses propriétés proviennent essentiellement de l'importance mathématique de sa relation avec une fonction d'énergie (cette énergie est détaillée dans le document au format pdf). Il est notamment prouvé que cette énergie est minimisée au centre de masse de chaque région, et que pour un ensemble de générateurs donnés, la fonction d'énergie est minimisée lorsque la partition en régions est un diagramme de Voronoi.

Diagramme de Voronoi centré.

L'objectif de ce stage consiste à recenser et à étudier les propriétés des diagrammes de Voronoï centrés, puis à analyser les algorithmes de construction de ces structures. Le plus connu est l'algorithme de Lloyd, qui consiste à alterner jusqu'à convergence une étape de déplacement de chaque générateur au centre de masse de sa cellule, avec une étape de mise à jour du diagramme de Voronoï (voir l'animation ci-dessous).

Si cet algorithme fonctionne bien en pratique, les propriétés et les conditions de convergence de l'algorithme de Lloyd sont encore mal connues. On étudiera notamment les questions suivantes: (i) quelles sont les conditions sur la fonction de densité pour garantir la convergence ? (ii) quel est le taux de convergence de l'algorithme de Lloyd ? (iii) comment se comporte l'algorithme en dimension 3, puis en dimension arbitraire ? (iv) sous quelles conditions l'algorithme de Lloyd atteint-il un minimum global de la fonction d'énergie ? (v) pour le cas uniforme, que devient la tesselation hexagonale dans le cas d'une distance non euclidienne ? Un volet plus expérimental consiste à vérifier la conjecture de Gersho qui établit un lien entre la fonction de densité et le diamètre de la cellule de Voronoï. Ce lien est notamment à la base de la propriété d'équi-répartition de la fonction de densité dans les cellules du diagramme de Voronoï.

Outils
PC / linux,
Langage C++,
Bibliothèque de programmes géométriques CGAL

Lieu
INRIA, Unité de Sophia-Antipolis
Projet GEOMETRICA
BP 93 - 06902 Sophia Antipolis, France

Contact
Pierre Alliez - chargé de Recherche
Projet GEOMETRICA
Tél : 04 92 38 76 77
E-mail: pierre.alliez@sophia.inia.fr

Relaxation de Lloyd en dimension 2. Asymptotiquement, et dans le cas d'une densité uniforme, la tessellation hexagonale est le point fixe de l'algorithme de Lloyd.