[The Laguerre diagram]
This Note presents a generalization of a known fast and robust algorithm of incremental construction of the Delaunay triangulation to the case of the regular triangulation of points in . In particular, the transport formula of simplex circumball centers are naturally extended to the case of the regular triangulation. The associated Laguerre diagram can then be obtained by duality from the regular triangulation. Some numerical examples of Laguerre diagrams in three dimensions are given.
Dans cette Note, nous proposons une généralisation d'un algorithme efficace et rapide de construction incrémentale de la triangulation de Delaunay au cas de la triangulation régulière d'un nuage de points dans dont le dual est le diagramme de Laguerre. En particulier, la formule du transport des centres des boules circonscrites aux simplexes de Delaunay se généralise naturellement au cas de la triangulation régulière. Des exemples numériques de diagrammes de Laguerre en trois dimensions sont présentés.
Accepted:
Published online:
Keywords: Computational solid mechanics, Delaunay triangulation, Regular triangulation, Voronoï diagram, Laguerre diagram, Power diagram
Houman Borouchaki 1; Nicolas Flandrin 2; Chakib Bennis 2
@article{CRMECA_2005__333_10_762_0, author = {Houman Borouchaki and Nicolas Flandrin and Chakib Bennis}, title = {Diagramme de {Laguerre}}, journal = {Comptes Rendus. M\'ecanique}, pages = {762--767}, publisher = {Elsevier}, volume = {333}, number = {10}, year = {2005}, doi = {10.1016/j.crme.2005.07.019}, language = {fr}, }
Houman Borouchaki; Nicolas Flandrin; Chakib Bennis. Diagramme de Laguerre. Comptes Rendus. Mécanique, Volume 333 (2005) no. 10, pp. 762-767. doi : 10.1016/j.crme.2005.07.019. https://comptes-rendus.academie-sciences.fr/mecanique/articles/10.1016/j.crme.2005.07.019/
[1] Sur la sphère vide, Izv. Akad. Nauk SSSR Otdel. Mat. Estestv. Nauk, Volume 7 (1934), pp. 793-800
[2] Nouvelles application des paramètres continus à la théorie des formes quadratiques. Deuxième mémoire : Recherches sur les paralléloèdres primitifs, J. Angew. Math., Volume 134 (1908), pp. 167-171
[3] Power diagrams: properties, algorithms and applications, SIAM J. Comput., Volume 16 (1987), pp. 78-96
[4] Géométrie Algorithmique, Ediscience International, 1995
[5] Optimal Delaunay point insertion, Int. J. Numer. Methods Engrg., Volume 39 (1996), pp. 3407-3437
[6] Computing Dirichlet tessellations, Comput. J., Volume 24 (1981), pp. 162-166
[7] Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes, Comput. J., Volume 24 (1981), pp. 167-172
[8] Triangulation automatique d'un polyèdre en dimension N, RAIRO Analyse Num., Volume 16 (1982) no. 3, pp. 211-242
[9] F. Avnaim, J.D. Boissonnat, O. Devillers, F.P. Preparata, M. Yvinec, Evaluating signs of determinants using single-precision arithmetic, Rapport de recherche INRIA, no 2306, 1994
[10] Delaunay's mesh of a convex polyhedron in dimension d. Application for arbitrary polyhedra, Int. J. Numer. Methods Engrg., Volume 33 (1992), pp. 975-995
[11] S. Balaven, C. Bennis, J.D. Boissonnat, M. Yvinec, Conforming orthogonal meshes, in: 11th International Meshing Roundtable, Ithaca, NY, USA, September 15–18, 2002, pp. 219–230
Cited by Sources:
Comments - Policy