Comptes Rendus
Diagramme de Laguerre
[The Laguerre diagram]
Comptes Rendus. Mécanique, Volume 333 (2005) no. 10, pp. 762-767.

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 Rd. 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 Rd 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.

Received:
Accepted:
Published online:
DOI: 10.1016/j.crme.2005.07.019
Mot clés : Mécanique des solides numérique, Triangulation de Delaunay, Triangulation régulière, Diagramme de Voronoï, Diagramme de Laguerre, Diagramme de puissance
Keywords: Computational solid mechanics, Delaunay triangulation, Regular triangulation, Voronoï diagram, Laguerre diagram, Power diagram

Houman Borouchaki 1; Nicolas Flandrin 2; Chakib Bennis 2

1 Université de technologie de Troyes, GSM-LASMIS, BP 2060, 10010 Troyes cedex, France
2 Institut français du pétrole, 1 et 4, avenue de Bois-Préau, 92852 Rueil-Malmaison cedex, France
@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},
}
TY  - JOUR
AU  - Houman Borouchaki
AU  - Nicolas Flandrin
AU  - Chakib Bennis
TI  - Diagramme de Laguerre
JO  - Comptes Rendus. Mécanique
PY  - 2005
SP  - 762
EP  - 767
VL  - 333
IS  - 10
PB  - Elsevier
DO  - 10.1016/j.crme.2005.07.019
LA  - fr
ID  - CRMECA_2005__333_10_762_0
ER  - 
%0 Journal Article
%A Houman Borouchaki
%A Nicolas Flandrin
%A Chakib Bennis
%T Diagramme de Laguerre
%J Comptes Rendus. Mécanique
%D 2005
%P 762-767
%V 333
%N 10
%I Elsevier
%R 10.1016/j.crme.2005.07.019
%G fr
%F CRMECA_2005__333_10_762_0
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] B. Delaunay Sur la sphère vide, Izv. Akad. Nauk SSSR Otdel. Mat. Estestv. Nauk, Volume 7 (1934), pp. 793-800

[2] G. Voronoï 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] F. Aurenhammer Power diagrams: properties, algorithms and applications, SIAM J. Comput., Volume 16 (1987), pp. 78-96

[4] J.-D. Boissonnat; M. Yvinec Géométrie Algorithmique, Ediscience International, 1995

[5] H. Borouchaki; P.L. George; S.H. Lo Optimal Delaunay point insertion, Int. J. Numer. Methods Engrg., Volume 39 (1996), pp. 3407-3437

[6] A. Bowyer Computing Dirichlet tessellations, Comput. J., Volume 24 (1981), pp. 162-166

[7] D.F. Watson Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes, Comput. J., Volume 24 (1981), pp. 167-172

[8] F. Hermeline 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] P.L. George; F. Hermeline 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