Sweep Line

Move an imaginary line across the plane and maintain a data structure describing what it currently touches. The continuous problem becomes a discrete sequence of events.

The skeleton

// 1. build events, sorted by the sweep coordinate
vector<Event> ev;
sort(ev.begin(), ev.end());
 
// 2. a status structure of currently-active objects
set<Segment, SweepCmp> status;
 
// 3. process
for (auto& e : ev) {
    if (e.isStart)  status.insert(e.obj);
    else            status.erase(e.obj);
    // answer whatever the event asks
}

Three design decisions: what is an event, what does the status structure hold, and what invariant does it maintain.

The classic applications

Problem	Events	Status	Time
Any two segments intersect?	endpoints	segments by $y$	$O(n\log n)$ (Shamos-Hoey)
Report all intersections	endpoints + intersections	segments by $y$	$O((n+k)\log n)$ (Bentley-Ottmann)
Area of a union of rectangles	vertical edges	segment tree with counts	$O(n\log n)$
Perimeter of a union of rectangles	same	same, tracking transitions	$O(n\log n)$
Count rectangle overlaps	same	segment tree with min-count	$O(n\log n)$
Closest pair	points by $x$	set of points by $y$	$O(n\log n)$
Maximum points in a window	window edges	count in a BIT	$O(n\log n)$
Skyline / building silhouette	building edges	multiset of heights	$O(n\log n)$
Point in polygon, many queries	polygon edges + queries	active edges	$O((n+q)\log n)$
Voronoi	sites + circle events	the beach line	$O(n\log n)$ (Fortune)
Rectangle stabbing queries	edges + queries	BIT over $y$	$O((n+q)\log n)$

Area of a union of rectangles

The template everyone should know:

// events: (x, y1, y2, +1 or -1) for the left and right edges
struct Ev { long long x, y1, y2; int type; };
sort(ev.begin(), ev.end(), [](const Ev& a, const Ev& b){ return a.x < b.x; });
 
long long area = 0, prevX = ev[0].x;
for (auto& e : ev) {
    area += covered() * (e.x - prevX);        // covered length from the segment tree
    update(e.y1, e.y2, e.type);
    prevX = e.x;
}

The segment tree stores, per node, a count of covering intervals and the covered length; covered() reads the root. Crucially, this tree never needs lazy propagation — because updates always come in matching $+1/-1$ pairs, a node’s count never goes negative and the covered length is recomputable from the count and the children.

void pull(int node, int l, int r) {
    if (cnt[node] > 0) len[node] = ys[r+1] - ys[l];
    else if (l == r)   len[node] = 0;
    else               len[node] = len[2*node] + len[2*node+1];
}

Coordinate-compress the $y$ values first.

Choosing the status structure

Need	Structure
Ordered active objects with neighbours	std::set
Count/sum over a coordinate range	BIT or segment tree
Covered length under $\pm 1$ updates	segment tree with counts (above)
Minimum/maximum active value	multiset or a heap with lazy deletion
$k$-th active value	PBDS or a BIT

Radial and angular sweeps

The sweep need not be a line. Rotating a ray around a point (sorting by angle) solves:

• visibility polygons,
• “how many points lie in some half-plane through this point”,
• maximum points inside an angular sector,
• counting triangles containing the origin.

Sort by angle with the exact cross-product comparator, not atan2.

Practical notes

Event ordering at equal coordinates

When several events share a sweep coordinate, their relative order matters. For rectangle unions, process all additions before all removals at the same $x$ (or you will miss zero-width overlaps). Encode the tiebreak explicitly in the comparator rather than relying on the sort being stable.

• Coordinate-compress early; it makes the status structure a small array.
• Use exact integer comparators; the whole point of a sweep is that the decisions are combinatorial.
• Think about whether the sweep should be over $x$, over angle, or over time (see offline dynamic connectivity, which is a sweep over the query timeline).

See also: Bentley-Ottmann · Segment Intersection · Offline Query Processing