From: Jeff Erickson Newsgroups: sci.math Subject: Re: Constrained tetrahedralization Date: Wed, 08 Oct 1997 13:49:53 -0400 Jeff Smith wrote: > I'm looking for software[*] or -- at the least -- a description of an > algorithm that will allow me to do constrained Delaunay > tetrahedralization. (Actually, it doesn't have to be strictly > Delaunay.) That is, given a set of 3D points and a set of faces > describing a surface, I'd like an algorithm that will tetrahedralize > the points such that no tetrahedra break this surface. Sorry, Luke, there is no such algorithm. There are simple polyhedra that cannot be broken into tetrahedra without adding extra vertices, which we computational geometers call "Steiner points". The simplest example is the so-called Schonhardt polyhedron: take a triangular prism and rotate one of the triangular faces, so that the sides buckle inwards. The same effect can be acheived with three tetrahedra that almost touch. For two more examples, see David Eppstein's web page "Three Untetrahedrizable Objects": http://www.ics.uci.edu/~eppstein/junkyard/untetra/ Jim Ruppert and Raimund Seidel proved that deciding whether a polyhedron can be trianglulated is NP-hard, even if you know in advance that adding one extra point in the interior is enough. Bernard Chazelle proved that to triangulate a collection of n faces, you may need Omega(n^2) Steiner points. > Help me, Obi-Wan; you're my only hope. These aren't the droids you're looking for. Move along. -- Jeff Erickson Center for Geometric Computing jeffe@cs.duke.edu Department of Computer Science http://www.cs.duke.edu/~jeffe Duke University