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
==============================================================================