Subject: CGAL users discussion list
List archive
- From: Manuel Caroli <>
- To:
- Subject: Re: [cgal-discuss] Time complexity of sweep
- Date: Mon, 14 Dec 2009 22:45:41 +0100
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
- [cgal-discuss] Time complexity of sweep, Ben Supnik, 12/14/2009
- Re: [cgal-discuss] Time complexity of sweep, Manuel Caroli, 12/14/2009
Archive powered by MHonArc 2.6.16.