Comptes Rendus
no. 10
Diagramme de Laguerre

Présenté par : Évariste Sanchez-Palencia

Houman Borouchaki1  ; Nicolas Flandrin2  ; Chakib Bennis2
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
Comptes Rendus. Mécanique, Volume 333 (2005) no. 10, pp. 762-767.

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.

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.

Reçu le :
Accepté le :
Publié le :
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

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

Modélisation géométrique des structures granulaires

Patrick Laug; Houman Borouchaki; Azeddine Benabbou; ...

C. R. Méca (2008)

Maillage simplicial d'un polyèdre arbitraire

Paul-Louis George; Houman Borouchaki

C. R. Math (2004)

Simplification des cartes géographiques par minimisation de la déformation locale

Pascal J. Frey; Houman Borouchaki

C. R. Math (2002)