1. Formal Invariant — Sweep-Line Status & No-Pushdown Coverage Segment Tree
Invariant 1: Bentley-Ottmann Local Adjacency Property
Suppose two segments $S_a$ and $S_b$ intersect at $x = x^*$. Immediately to the left of $x^*$ (after processing all events with $x < x^*$), $S_a$ and $S_b$ must be immediately adjacent in the vertical sweep-line status BST! Therefore, checking only newly adjacent pairs upon segment insertion, deletion, or intersection swap detects all $K$ intersections in $O((N + K) \log N)$ time.
Invariant 2: Klee's Measure Segment Tree (No Lazy Propagation Required!)
When sweeping vertical edges of $N$ rectangles $(x_1, +1, [y_1, y_2])$ and $(x_2, -1, [y_1, y_2])$, every $-1$ deletion removes an interval that was previously inserted as $+1$. Each Segment Tree node $u$ stores:
- $\text{cnt}[u] \ge 0$: how many active rectangles completely cover node $u$'s canonical $y$-interval.
- $\text{len}[u]$: total covered length inside $u$'s subtree: if $\text{cnt}[u] > 0$, then $\text{len}[u] = Y[r+1] - Y[l]$; otherwise $\text{len}[u] = \text{len}[2u] + \text{len}[2u+1]$.
Because we only ever query the global root $\text{len}[1]$, we never need lazy pushdown!
2. Sweep-Line Architecture for Area of Union of Rectangles
[x1, x2] x [y1, y2]"] --> Events["Create 2N Vertical Events:
(x1, +1, y1, y2) and (x2, -1, y1, y2)
+ Coordinate Compress Y"] Events --> Sweep["Sweep Events i = 0..2N-1:
Area += segtree.root_len() * (x_i - x_{i-1})"] Sweep --> Update["Update Segment Tree on [y1, y2] with +1 / -1
Recalculate len[u] in O(log N)"] Update --> Sweep
3. Closest Pair of Points via Sweep-Line in $O(N \log N)$
Another classic sweep-line application finds the **Closest Pair of Points** among $N$ points without divide-and-conquer: sort points by $x$, maintain a sliding window of points with $x_i - x_j < d$ inside a std::set ordered by $y$, and for each point $P_i$, query the std::set range $[y_i - d, y_i + d]$. By a geometric packing argument, at most **6 points** can exist inside the $d \times 2d$ bounding box with pairwise distance $\ge d$, so the inner loop executes at most 6 iterations per point!
4. Hardware & Memory Access Reality
Coordinate Compression + Flat Array Segment Tree
In Klee's Measure Problem, $y$-coordinates can span $[-10^9, 10^9]$, but at most $2N$ distinct $y$-coordinates exist. Sorting and deduplicating them into a flat array Y[0..M-1] maps every elementary interval $[Y[k], Y[k+1]]$ to leaf $k$ of a static $4M$-element array Segment Tree, running $10\times$ faster than pointer-based dynamic trees.
5. Complexity Matrix
Trace 2D cross-product orientation tests cross(O, A, B) = (Ax-Ox)(By-Oy) - (Ay-Oy)(Bx-Ox) to prune clockwise interior vertices and detect sweep-line segment intersections.
Invariant & State
| Sweep-Line Problem | Time Complexity | Space Complexity | Sweep-Line Status Structure |
|---|---|---|---|
| Any Two Segments Intersect (Shamos-Hoey) | O(N log N) | O(N) | Balanced BST (std::set) ordered by $y(x)$ |
| All $K$ Segment Intersections (Bentley-Ottmann) | O((N + K) log N) | O(N + K) | Balanced BST + Priority Queue of Events |
| Area / Perimeter of Union of $N$ Rectangles | O(N log N) | O(N) | Coordinate-Compressed Coverage Segment Tree |
| 2D Closest Pair of Points | O(N log N) | O(N) | Sliding-Window std::set ordered by $y$ |
6. Production-Grade C++20 Implementation (Area of Union of Rectangles)
#include <vector>
#include <cstdint>
#include <algorithm>
struct Rect {
int64_t x1, y1, x2, y2; // [x1, x2] x [y1, y2] with x1 < x2, y1 < y2
};
int64_t rectangle_union_area(const std::vector<Rect>& rects) {
if (rects.empty()) return 0;
struct Event {
int64_t x;
int type; // +1 for entering left edge, -1 for leaving right edge
int64_t y1, y2;
bool operator<(const Event& o) const {
return x != o.x ? x < o.x : type > o.type;
}
};
std::vector<Event> events;
std::vector<int64_t> coords_y;
events.reserve(rects.size() * 2);
coords_y.reserve(rects.size() * 2);
for (const auto& r : rects) {
if (r.x1 >= r.x2 || r.y1 >= r.y2) continue;
events.push_back({r.x1, +1, r.y1, r.y2});
events.push_back({r.x2, -1, r.y1, r.y2});
coords_y.push_back(r.y1);
coords_y.push_back(r.y2);
}
if (events.empty()) return 0;
std::sort(events.begin(), events.end());
std::sort(coords_y.begin(), coords_y.end());
coords_y.erase(std::unique(coords_y.begin(), coords_y.end()), coords_y.end());
const int m = static_cast<int>(coords_y.size()) - 1; // Number of elementary y-intervals
if (m <= 0) return 0;
std::vector<int> cnt(4 * m, 0);
std::vector<int64_t> len(4 * m, 0);
auto pull = [&](int u, int l, int r) {
if (cnt[u] > 0) {
len[u] = coords_y[r + 1] - coords_y[l];
} else if (l == r) {
len[u] = 0;
} else {
len[u] = len[2 * u] + len[2 * u + 1];
}
};
auto update = [&](auto& self, int u, int l, int r, int ql, int qr, int delta) -> void {
if (ql <= l && r <= qr) {
cnt[u] += delta;
pull(u, l, r);
return;
}
int mid = l + (r - l) / 2;
if (ql <= mid) self(self, 2 * u, l, mid, ql, qr, delta);
if (qr > mid) self(self, 2 * u + 1, mid + 1, r, ql, qr, delta);
pull(u, l, r);
};
int64_t total_area = 0;
int64_t prev_x = events[0].x;
for (const auto& ev : events) {
total_area += len[1] * (ev.x - prev_x);
prev_x = ev.x;
int yl = static_cast<int>(std::lower_bound(coords_y.begin(), coords_y.end(), ev.y1) - coords_y.begin());
int yr = static_cast<int>(std::lower_bound(coords_y.begin(), coords_y.end(), ev.y2) - coords_y.begin()) - 1;
if (yl <= yr) {
update(update, 1, 0, m - 1, yl, yr, ev.type);
}
}
return total_area;
}Production Pitfall — Point-Based vs Elementary-Interval Indexing in Segment Trees
In a standard point Segment Tree, leaf $i$ represents point $Y[i]$, so $[Y[i], Y[i+1]]$ leaves a gap between $Y[i]$ and $Y[i+1]$! In Klee's Measure Problem, leaf $i$ MUST represent the continuous elementary interval $[Y[i], Y[i+1]]$ of length coords_y[i + 1] - coords_y[i]. Consequently, a rectangle spanning $[y_1, y_2]$ updates leaf indices [idx(y1), idx(y2) - 1], not [idx(y1), idx(y2)]!