From: jeffe@ocarina.CS.Berkeley.EDU (Jeff Erickson)
Newsgroups: comp.graphics.algorithms
Subject: Re: Help! Triangulation of polygon
Date: 21 Feb 96 23:33:19 GMT

Alistair Imrie <alistair@articad.demon.co.uk> writes:

>Given an arbitrary (3D) polygon expressed as an array of x, y, z
>coordinates, how can I divide the polygon into constituent triangles?

In general, you can't!!  If the polygon is knotted, there is no
triangulation, even if you allow extra vertices.  There are examples
of unknotted 3D polygons that can't be triangulated unless you add
extra vertices.

Gill Barequet, Matt Dickerson, and David Eppstein have recently shown
that deciding if a 3D polygon can be triangulated without extra
vertices is NP-complete.  Unknotted polygons can always be
triangulated if you add enough extra vertices, but Jack Snoeyink has
shown that you might need exponentially many of them.

Nobody knows how hard it is to decide if a 3D polygon is knotted.
(I'm reasonably sure it can be done in exponential time.)

Of course, if your 3D polygon is contained in a plane, then it's
really a 2D polygon, it can always be triangulated, and you should
read the bloody FAQ.

See:

G. Barequet, M. Dickerson, and D. Eppstein.
	On triangulating three-dimensional polygons.
	Proc. 12th Annu. ACM Symp. Comp. Geom. (1996), to appear. 

J. Snoeyink.
	A trivial knot whose spanning disks have exponential size.
	Proc. 6th Annu. ACM Sympos. Comput. Geom. (1990), pages 139--147.


-- 
Jeff Erickson
jeffe@cs.berkeley.edu
http://www.cs.berkeley.edu/~jeffe

==============================================================================

From: orourke@grendel.csc.smith.edu (Joseph O'Rourke)
Newsgroups: comp.graphics.algorithms
Subject: Re: Help! Triangulation of polygon
Date: 26 Feb 1996 02:31:40 GMT

In article <jeffe.824945599@ocarina>,
Jeff Erickson <jeffe@ocarina.CS.Berkeley.EDU> wrote:
>Nobody knows how hard it is to decide if a 3D polygon is knotted.
>(I'm reasonably sure it can be done in exponential time.)

I just saw this paper title at a future AMS conference:
"Detecting the unknot in polynomial time" by Delman and Wolcott.
I intend to try to find an abstract of the paper, and write to
the authors, but from the title it sounds like the problem
is polynomial.

==============================================================================