From: eppstein@euclid.ics.uci.edu (David Eppstein)
Subject: Re: Triangulation of polyhedral domains.
Date: 27 May 1999 09:25:56 -0700
Newsgroups: sci.math
Carl Christian Kjelgaard Mikkelsen writes:
> I suspect that it is allways possible to triangulate a bounded domain
> with a piecewise linear boundary.
> I would like a refence to a proof.
There is a proof (not original) in my survey "Mesh generation and
optimal triangulation", with Marshall Bern, in _Computing in Euclidean
Geometry_, 2nd ed., World Scientific 1995, pp. 47-123
(see http://www.ics.uci.edu/~eppstein/pubs/BerEpp-CEG-95.pdf)
Here's the idea: let p be the leftmost vertex of the domain, and let q
and r be the two adjacent vertices on either side of p. It may be
possible that you can safely add edge qr, splitting the problem into two
smaller subproblems. But if not, qr is blocked by some other edges that
cross into triangl pqr. In this case, let s be the vertex in triangle pqr
that is farthest from line qr; it must be safe to add edge ps, because
any edge that would block it would have an even farther vertex.
--
David Eppstein UC Irvine Dept. of Information & Computer Science
eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/