Premium
‘Ultimate’ robustness in meshing an arbitrary polyhedron
Author(s) -
George P. L.,
Borouchaki H.,
Saltel E.
Publication year - 2003
Publication title -
international journal for numerical methods in engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.421
H-Index - 168
eISSN - 1097-0207
pISSN - 0029-5981
DOI - 10.1002/nme.808
Subject(s) - polyhedron , delaunay triangulation , pitteway triangulation , robustness (evolution) , bowyer–watson algorithm , minimum weight triangulation , constrained delaunay triangulation , surface triangulation , mathematics , boundary (topology) , triangle mesh , mesh generation , triangulation , algorithm , dual graph , computer science , mathematical optimization , combinatorics , geometry , polygon mesh , graph , finite element method , mathematical analysis , planar graph , engineering , biochemistry , chemistry , structural engineering , gene
Given a boundary surface mesh (a set of triangular facets) of a polyhedron, the problem of deciding whether or not a triangulation exists is reported to be NP‐hard. In this paper, an algorithm to triangulate a general polyhedron is presented 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 points defined in the previous step. Following this phase, the resulting mesh conforms to the given boundary surface mesh. The proposed method results in a discussion of theoretical interest about existence and complexity issues. In practice, however, the method should provide what we call ‘ultimate’ robustness in mesh generation methods. Copyright © 2003 John Wiley & Sons, Ltd.