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/