Simplicial mesh of an arbitrary polyhedron

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. (C) 2004 Academie des sciences. Publie par Elsevier SAS. Tous droits reserves.