Prev: use of goto in C
Next: Sorting in linear time ...
From: Daniel Lidstrom on 29 Apr 2010 08:19
On 27 Apr, 09:49, Ralph Boland <rpbol...(a)gmail.com> wrote:
> On Apr 26, 6:16 am, Daniel Lidstrom <dlidst...(a)gmail.com> wrote:
>
> > Hi,
>
> > apparently there is an O(N) algorithm available for triangulating a
> > polygon. It was discovered by Bernard Chazelle in 1990. The paper [1]
> > is 40 pages! I wanted to see this remarkable algorithm. However, I
> > read that it is too complex even to implement. Naturally I am
> > wondering how this can be. Can someone explain? Also, out of
> > curiosity, are there known algorithms in other domains that are non-
> > implementable?
>
> > [1]http://www.cs.princeton.edu/~chazelle/pubs/polygon-triang.pdf
>
> > --
> > Daniel
>
> I have read  Chazelle's paper and can say that it is implementable if
> you have
> the time to do the work.  But the algorithm is very complex and
> not worth the EFFORT to do so.  There are lots of algorithms in papers
> on algorithms that are like this but Chazelle's algorithm is worse
> than
> most.  Even if you implemented Chazelle's algorithm you would then
> find that in practice it is slower than a number of much simpler
> non-linear competitors.  Thus you would never use it.
>
> By the way, my favourite triangulation alorithm is:
>      B. CHAZELLE, J. INCERPI, Triangulation and shape complexity.
> ACM Transactions on Graphics, 3 (1984), 135-152.
>
> It was implemented  (1600 lines of C) and I claim it runs in linear
> time in practice though of course I have no proof of this.
> My guess would be that the linear time algorithm would take at
> least 25000 lines of  C  and then be shown to be much slower than
> the shape complexity algorithm among others.
>
> Ralph Boland

Hi Ralph,

thanks for your interesting insight into this particular algorithm. I
didn't think I would get an answer from a person with a Ph.D. in
computational geometry. May I ask if you have a personal webpage with
some of your work?

Thanks!

--
Daniel
First  |  Prev  | 
Pages: 1 2 3
Prev: use of goto in C
Next: Sorting in linear time ...