CGAL users discussion list

[Ben Supnik <>]

If the arrangements are simple and the lines don't overlap, you might 
have better luck with by insert-sweep, then examine.

The total time to sweep ALL the lines at once should be significantly 
less than the time to "walk" each line individually.

And...the guts matter too - in my experience, sweep is faster than walk 
in its use of geometric primitives.

My suggestion:

Do an insert_curves on the arrangement with the list of lines, and just 
see how long it takes.  If it is faster than your alg running time, it'd 
be worth exploring whether you could then get your results from the 
results of the sweep.  If you already have the lines and arrangement, 
writing this test code to test speed would be pretty quick.

cheers
ben


Marco Aurelio Sterpa wrote:
> I just consider simple arrangements, so every line intersect each other 
> in exactly one point, I don't know if this can help. Anayway what I have 
> to compute is the set of k-levels for a given arrangement, this is a 
> simple O(n^2) algorithm, but I guess there's another randomized with 
> better complexity. Do you know is something offered by the library to do 
> this stuff? This is part of a little bigger algorithm and it seems that 
> this for iteration is the one who takes the longest time to compute.
>
> 2009/11/5 Ben Supnik < 
> <mailto:>>