CGAL users discussion list

[Manuel Caroli <>]

Hi Ben,

in terms of O notation this does not change anything:
The number of end-points is in O(n). The number of common end-points, 
too, of course. So all this can change the expression only by a constant 
factor, which does not change the asymptotic behavior.

best

Manuel


Ben Supnik wrote:
> Hi Y'all,
>
> The CGAL manual lists the time complexity of sweep-line algorithms as
>
> O((n+k) log n)
>
> where n is the number of curves, and k is the number of intersections.
>
> Here are my stupid questions:
>
> 1. Do two curves with a common end-point count as an intersection?  (I 
> would imagine yes?)
>
> 2. Do the ends of the curves count as intersections (e.g. vertices in 
> the arrangement with degree 1)?
>
> Thanks!
> Ben