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

From: Thorsten Ottosen (thorsten.ottosen_at_[hidden])
Date: 2007-03-23 11:54:58

Olaf Krzikalla skrev:
> Hi,
> 
> Thorsten Ottosen wrote:
>>>> What I would like to know is if typically all objects is 
>>>> inside intrusive containers; also for the use of 2,3, or 4 simultaneous 
>>>> containers.
>>> I wouldn't say so. In fact, at least one triangulation algorithm needs 
>>> to maintain and iterate over a list of all concave vertices of a polygon 
>>> again and again (the list becomes smaller during the triangulation 
>>> process). But usually in a typical polygon there are much more convex 
>>> vertices. Thus just marking the vertices with a flag was no option, 
>>> because you'd have to iterate over the whole set of vertices just to 
>>> (re)find the concave ones. A "std::list<Vertex*> concaves;" could help 
>>> and in usual cases generate less memory overhead than the intrusive 
>>> approach.  However, the triangulation algorithm also needs to detect, 
>>> whether a given vertex was concave. By using the linked() property of 
>>> the intrusive node used by the "concave ilist" it was possible to have a 
>>> very fast test for that. IMHO a typical example of the classic space vs. 
>>> time tradeoff.
>>
>> Ok. How badly would the algorithm perform if these two types of test 
>> where only O(lg N) ?
> 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?

-Thorsten