From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Splitting polygons Date: 27 Nov 1996 14:07:35 GMT In article <57fdc1$77@gap.cco.caltech.edu>, Douglas J. Zare wrote: >That's probably useless to you, as you are probably trying to triangulate >a polygon in the first place. If you use the above inductively, it takes >time quadratic in the number of sides. You can do much better than that, >but it is difficult to do this and worry about special cases--many >implemented and published algorithms do not work. Since this problem is >extremely common, you should look up what is done in any of the standard >programming references, such as the one by Knuth. Is it really possible to "do much better than that"? I speak as one who is not well versed in this area and has been guilty of suggesting algorithms which do not work. My concern is with regions like this: join the ends of this chain: __ ____ ____ ____ ____ ____ ____ ____ ____ ____ __ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ so that the points face inward. Allow the tips of the points to position themselves more or less randomly around the center of the resulting figure. Is it really possible to determine a triangulation using an algorithm which is not, in the worst case, quadratic in the number of sides? dave ============================================================================== From: eppstein@euclid.ICS.UCI.EDU To: rusin@vesuvius.math.niu.edu Subject: Splitting polygons Date: Wed, 27 Nov 1996 10:13:16 -0800 Is it really possible to determine a triangulation using an algorithm which is not, in the worst case, quadratic in the number of sides? Yes. It can be done in linear time (theoretically), or close to linear time (more practically). Read the FAQ for comp.graphics.algorithms. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/ ============================================================================== From: "Douglas J. Zare" Date: Sun, 1 Dec 1996 17:25:36 -0800 To: rusin@vesuvius.math.niu.edu Subject: Re: Splitting polygons Newsgroups: sci.math >In article <57fdc1$77@gap.cco.caltech.edu>, >Douglas J. Zare wrote: > >>That's probably useless to you, as you are probably trying to triangulate >>a polygon in the first place. If you use the above inductively, it takes >>time quadratic in the number of sides. You can do much better than that, >>but it is difficult to do this and worry about special cases--many >>implemented and published algorithms do not work. Since this problem is >>extremely common, you should look up what is done in any of the standard >>programming references, such as the one by Knuth. > >Is it really possible to "do much better than that"? I speak as one who >is not well versed in this area and has been guilty of suggesting >algorithms which do not work. My concern is with regions like this: >join the ends of this chain: > __ ____ ____ ____ ____ ____ ____ ____ ____ ____ __ > \/ \/ \/ \/ \/ \/ \/ \/ \/ \/ > >so that the points face inward. Allow the tips of the points to >position themselves more or less randomly around the center of the >resulting figure. Is it really possible to determine a triangulation >using an algorithm which is not, in the worst case, quadratic in the >number of sides? Yes. The reason that I was vague was that I remembered that nlogn is not too hard (to prove, rather than implement, and this should be what is in Knuth), but there have been improvements. In particular, there was a probabalistic algorithm which took n log*n time. (http://www,inria.fr/rapports/sophia/RR-1412.html) I don't recall the reference, but in the talk he gave on the history of triangulation algorithms at the RGI at Smith College in 1993, J. O'Rourke mentioned that it is possible to make the algorithm deterministic. I believe that he said that there was a new, surprising, linear-time algorithm. Doug ==============================================================================