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