Comptes Rendus
Analyse numérique
Maillage simplicial d'un polyèdre arbitraire
[Simplicial mesh of an arbitrary polyhedron]
Comptes Rendus. Mathématique, Volume 338 (2004) no. 9, pp. 735-740.

Issues related to the existence of a triangulation of an arbitrary polyhedron are addressed. Given a boundary surface mesh (a set of triangular facets), the problem to decide whether or not a triangulation (with no internal points apart from the Steiner points) exists is reported to be NP-hard. In this paper, an algorithm to triangulate a general polyhedron is used which makes use of a classical Delaunay triangulation algorithm, a phase for recovering the missing boundary facets by means of facet partitioning and a final phase that makes it possible to remove the additional (non-Steiner) points previously defined so as to recover the initial boundary mesh thus resulting in a mesh of the given polyhedron.

On discute de l'existence d'un maillage simplicial pour un polyèdre arbitraire. Étant donné un maillage (en triangles) conforme de la surface du domaine, décider s'il existe une triangulation (sans point interne autre que de Steiner) de ce domaine est un problème NP-complet. Ce papier décrit une méthode qui construit une telle triangulation, assurant ainsi son existence. La méthode proposée comprend trois étapes. En premier, un algorithme de triangulation de Delaunay est appliqué aux points donnés, ensuite une étape de regénération des éléments de la surface est faite qui conduit à la partition des faces initiales. Enfin, une dernière étape permet de supprimer les points (sauf ceux de Steiner) ajoutés lors de cette partition.

Received:
Accepted:
Published online:
DOI: 10.1016/j.crma.2003.12.033
Paul-Louis George 1; Houman Borouchaki 2

1 INRIA – Rocquencourt, Projet Gamma, BP 105, 78153 Le Chesnay cedex, France
2 Université de technologie de Troyes, GSM-LASMIS, BP 2060, 10010 Troyes cedex, France
@article{CRMATH_2004__338_9_735_0,
     author = {Paul-Louis George and Houman Borouchaki},
     title = {Maillage simplicial d'un poly\`edre arbitraire},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {735--740},
     publisher = {Elsevier},
     volume = {338},
     number = {9},
     year = {2004},
     doi = {10.1016/j.crma.2003.12.033},
     language = {fr},
}
TY  - JOUR
AU  - Paul-Louis George
AU  - Houman Borouchaki
TI  - Maillage simplicial d'un polyèdre arbitraire
JO  - Comptes Rendus. Mathématique
PY  - 2004
SP  - 735
EP  - 740
VL  - 338
IS  - 9
PB  - Elsevier
DO  - 10.1016/j.crma.2003.12.033
LA  - fr
ID  - CRMATH_2004__338_9_735_0
ER  - 
%0 Journal Article
%A Paul-Louis George
%A Houman Borouchaki
%T Maillage simplicial d'un polyèdre arbitraire
%J Comptes Rendus. Mathématique
%D 2004
%P 735-740
%V 338
%N 9
%I Elsevier
%R 10.1016/j.crma.2003.12.033
%G fr
%F CRMATH_2004__338_9_735_0
Paul-Louis George; Houman Borouchaki. Maillage simplicial d'un polyèdre arbitraire. Comptes Rendus. Mathématique, Volume 338 (2004) no. 9, pp. 735-740. doi : 10.1016/j.crma.2003.12.033. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2003.12.033/

[1] J.D. Boissonnat; M. Yvinec Géométrie Algorithmique, Ediscience, Paris, 1995

[2] H. Borouchaki; P.L. George; S.H. Lo Boundary enforcement by facet splits in Delaunay based mesh generation, 7th Inter. Conf. on Numerical Grid Generation in Computational Field Simulations, Whistler, BC, Canada, September 2000, pp. 203-221

[3] B. Chazelle Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm, SIAM J. Comput., Volume 13 (1984) no. 3, pp. 488-507

[4] B. Chazelle Triangulating a simple polygon in linear time, Discrete Comput. Geom., Volume 6 (1991), pp. 485-524

[5] B. Chazelle; L. Palios Triangulating a nonconvex polytope, Discrete Comput. Geom., Volume 5 (1990), pp. 505-526

[6] C. Hazlewood Approximating constrained tetrahedrizations, Computer Aided Geometric Design, vol. 10, Academic Press, 1993, pp. 67-87

[7] P.L. George, H. Borouchaki, E. Saltel, Maillage simplicial d'un polyèdre arbitraire. Partie II : Construction et exemples, Rapport de recherche INRIA, RR-4398, 2002

[8] P.L. George; F. Hecht; E. Saltel Automatic mesh generator with specified boundary, Comput. Methods Appl. Mech. Engrg., Volume 92 (1991), pp. 269-288

[9] M. Murphy; D.M. Mount; C.W. Gable A point-placement strategy for conforming Delaunay tetrahedralization, Proc. 11th ACM-SIAM Symposium on Discrete Algorithms, 2000, pp. 67-74

[10] Ph.P. Pebay, Delaunay-admissibilié a priori en dimensions 2 et 3, Thèse de l'Université Pierre et Marie Curie, Paris, 2000

[11] F.P. Preparata; M.I. Shamos Computational Geometry, an Introduction, Springer-Verlag, 1985

[12] J. Ruppert; R. Seidel On the difficulty of triangulating three-dimensional nonconvex polyhedra, Discrete Comput. Geom., Volume 7 (1992), pp. 227-253

[13] E. Schönhardt Über die Zerlegung von Dreieckspolyedern, Math. Ann., Volume 98 (1928), pp. 309-312

[14] N.P. Weatherill; O. Hassan Efficient three-dimensionnal Delaunay triangulation with automatic point creation and imposed boundary constraints, Int. J. Numer. Methods Engrg., Volume 37 (1994), pp. 2005-2039

Cited by Sources:

Comments - Policy


Articles of potential interest

Diagramme de Laguerre

Houman Borouchaki; Nicolas Flandrin; Chakib Bennis

C. R. Méca (2005)


Enhancement of the accuracy of numerical field computation using an adaptive three-dimensional remeshing scheme

Houman Borouchaki; Thomas Grosges; Dominique Barchiesi

C. R. Méca (2010)


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

Pascal J. Frey; Houman Borouchaki

C. R. Math (2002)