26 Mar
2007
26 Mar
'07
12:12 p.m.
Hmm, from a quick glance I can definitely say it raises from O(m*n) to at least O(m*n*lg(n)), maybe even worse (m being the number of all veritces in a polygon, n being the number of concave vertices in it).
Ok. And what are typical values of m and n? Hard to say. Depends on the application domain. At http://www.cs.man.ac.uk/~toby/alan/software/
Hi, Thorsten Ottosen wrote: there is an example with m=2763, n~1000. I remember of practical problems with m=200 and m~n (where a strict O(m*lg(m)) algorithm would have done better, but we needed a 'nice' triangulation). Best Olaf