Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Time complexity of sweep

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Time complexity of sweep


Chronological Thread 
  • 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




Archive powered by MHonArc 2.6.16.

Top of Page