Re: [Boost-users] [review] intrusive container comments

From: Olaf Krzikalla (krzikalla_at_[hidden])
Date: 2007-03-26 08:12:56

Hi,

Thorsten Ottosen wrote:
>>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/
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