Sweeping a line across the plane
The line sweep technique imagines a vertical line moving across the plane from left to right. Instead of comparing every pair of objects, you handle events in the order they occur along the axis. Between events nothing interesting changes, so you only act at the event points.
Events and the active set
You collect event coordinates, sort them, then process them in order while maintaining an active set of objects the sweep currently touches.
- For interval problems, a start event adds an interval and an end event removes one. The active set size at any moment is how many intervals overlap there.
- For rectangle area, vertical edges are events and the active set tracks covered vertical spans.
- For closest pair, the sweep keeps a window of nearby points and only compares within it.
Why it helps
Sorting the events costs a log linear amount, and each event does a small amount of work on the active set, often using a balanced structure. This replaces a quadratic all pairs comparison with something far cheaper.
Key idea
Turn objects into sorted events and sweep across them, maintaining an active set so each event does light work and avoids comparing every pair.