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 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 , Jeff Erickson 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. ==============================================================================