Centre de Mathématiques et de Leurs Applications

Séminaire du jeudi 06 mai 2010

Orateur: Bruno Levy

Titre: Sur les diagrammes de Voronoi centroidaux

Résumé:

Nous nous interessons a plusieurs proprietes des diagrammes de Voronoi centroidaux ainsi qu'aux algorithmes permettant de les construires dans differentes configurations. Les applications concernent le maillage de surfaces et de volumes.

Etant donne un ensemble de points $X=(x_1, x_2, ..., x_n)$, le diagramme de Voronoi $Vor(X)$ est dit "centroidal" si la position de chaque site $x_i$ coincide avec le centre de gravite $g_i = \int \Omega_i xdx / \int \Omega_i dx$ de la cellule de Voronoi correspondante.

En termes de theorie de l'echantillonage, les diagrammes de Voronoi centroidaux correspondent a des points critiques de la puissance du bruit d'echantillonage $f(X)$ definie par $f(X) = \sum_i \int \Omega_i \| x - x_i \|^2 dx$, a savoir la somme des moments d'inertie de chaque cellules de Voronoi par rapport a son site $x_i$.
Nous montrons que la fonction $f$ est de classe $C^2$, ce qui permet son optimisation numerique a l'aide de methodes de type Newton.

* Dans le cas d'une surface $S$ plongee dans $IR^3$, nous nous interessons aux diagrammes de Voronoi restreint a S $Vor(X)|_S$, a savoir la partition de $S$ engendree par l'intersection entre $S$ et les cellules $\Omega_i$ d'un diagramme de Voronoi 3D $Vor(X)$. Un diagramme de Voronoi restreint $Vor(X)|S$ est centroidal si chaque site $x_i$ coincide avec le centre de gravite de la cellule de Voronoi restreinte $\Omega_i \cap S$. Nous etudions un algorithme permettant de calculer le diagramme de
Voronoi restreint $Vor(X)|S$ dans le cas ou $S$ est une surface lineaire par morceaux. Nous presentons une application au re-maillage de surfaces.

* De maniere similaire, dans le cas d'un volume $V = Int(S)$ correspondant a l'interieur d'une surface
lineaire par morceaux, nous etudions un algorithme permettant de calculer l'intersection $Vor(X) \cap V$ entre le le diagramme de Voronoi et le volume. Nous
presentions une application au maillage de volumes.