Algorithme de Llyod dans l'espace périodique 3D

Lloyd's algorithm in the 3D periodic space

Contact : Monique Teillaud <Monique(dot)Teillaud(at)inria.fr>

Lloyd's algorithm, or Voronoi relaxation, is used in several applications to compute centroidal Voronoi tessellations. Its convergence has been shown in one dimension. In higher dimensions, one of the problems is due to the fact that the studied domain has a boundary. A package computing 3D periodic Delaunay triangulations has recently been integrated in CGAL, the Computational Geometry Algorithms Library. A demo of Lloyd's algorithm is available. The work will consist in experimentally stuying the convergence of Lloyd's algorithm in the 3D periodic setting, which avoids boundaries. The same experiments will be run with the optimal Delaunay triangulation. In both cases, the distribution of angles will be studied. Also, a possible convergence to some crystalline structures will be examined.

Ce stage peut être abordé en L3 ou en M1, à des degrés d'approfondissement différents.
See also other topics: internship, PhD.

References
on periodic triangulations

• Manuel Caroli and Monique Teillaud. Computing 3D Periodic Triangulations. In Proceedings 17th European Symposium on Algorithms, volume 5757 of Lecture Notes in Computer Science, pages 37-48, 2009. Full version.
• CGAL 3D periodic triangulations manual
• See also

• Qiang Du, Maria Emelianenko, and Lili Ju. Convergence properties of the Lloyd algorithm for computing the centroidal Voronoi tessellations, SIAM J. Numer. Anal., 44(1):102-119, 2006.
• L. Chen and J. Xu. Optimal Delaunay triangulations. Journal of Computational Mathematics, 22(2):299-308, 2004.

To know more about :

Site of the CGAL Open Source project Slides: Introduction to CGAL.

Knowledge involved:
- C++ (templates, etc)
- mathematical aspects (combinatorics, geometry).
A good level in both aspects is necessary.