Sweep Line Technique
The sweep line technique solves geometry and range problems by scanning across the input in order, as if a line were sweeping over it.
4 INTERVALS · 8 EVENTS
INTERVAL OPENS
ACTIVE 1 · PEAK 1
x = 1: interval 1 starts. Active count rises to 1. That is a new maximum.
Next
x = 1: interval 4 starts. Active count rises to 2. That is a new maximum.
Intuition
Instead of checking every possible coordinate or point in a 2D plane, imagine a vertical line sweeping across the plane from left to right.
We only stop at "interesting" points (Events). By processing events in sorted order, we can maintain the state of the active elements efficiently.
Concept
Key Components:
- Events: Points where status changes (Start of interval, End of interval, Intersection point).
- Event Queue: A sorted list of all future events.
- Active Set (State): Data structure tracking currently active objects intersecting the sweep line (e.g., BST, Scalar Count).
How it Works
The visualizer shows the line moving across intervals.
- Start Event: Add interval to active set.
- End Event: Remove interval from active set.
- Query: At any point, the active set tells us how many intervals overlap.
Step-by-Step Breakdown
1. Decompose objects into Events (Start/End).
2. Sort Events by coordinate (usually X).
3. Iterate through sorted events.
4. Update Active Set based on event type.
When to Use
- Finding overlapping intervals.
- Closest Pair of Points.
- Union of Rectangles Area.
- Convex Hull construction.
When NOT to Use
- When objects are not static (dynamic updates).
- When dimensions are higher than 2D (gets complex fast).
How to Identify
"Overlapping rectangles", "Interval intersection", "Points in plane".
Applying for software engineering roles? Free, no sign-up:
AI resume checker — match your resume to the job description
Compare its cost with every other algorithm in the Big O cheat sheet.