AlgoScope

Sweep Line

Move a line across the plane, processing events in order and maintaining an active set.

Computational geometry, technique, advanced
Insert AB at x = 0.ABCDEFGH
Insert AB at x = 0.ABCDEFGH

Plane Geometry: Sweep finds a crossing at the second event

Decision, step 2 of 4

x = 0: AB begins. It enters the active order by its height here, giving AB. It has no neighbour yet, so there is nothing to test.

How plane geometry works

Cost

Best
O(n log n)
Average
O((n + k) log n)
Worst
O((n + k) log n)
Space
O(n)

Leads to

Topics that need this one first.

Taught by the same lesson

Plane Geometry covers these too, in the same run.