Klee's Measure Problem

Suppose you have a stack of sticky notes scattered across a table, some overlapping. You want to know the total table area they cover — not the sum of their individual areas, but the net covered area after accounting for every overlap.

That is Klee's measure problem, posed by Victor Klee in 1977. The input is a list of n axis-aligned rectangles, possibly overlapping. The output is a single number: the total area of their union.

The naive approach — summing all rectangle areas and then subtracting overlaps — runs into an inclusion-exclusion nightmare with up to $2^{n}$ terms. Yet the problem is solved, and solved beautifully: a sweepline algorithm computes the answer in $O(n \log n)$ time. The key insight is to drag an imaginary vertical line across the plane and maintain, as the line moves, exactly how much of it is currently covered by some rectangle.

This is not just an abstract puzzle. Klee's problem shows up in circuit design, database query planning, computer graphics, and anywhere that areas of influence overlap.

Click Add rectangle to drop a randomly placed rectangle on the canvas. As each rectangle is added the sweepline (the vertical dashed line) scans from left to right, tallying the height covered at every x-coordinate. The reported area is always the exact union area — overlaps are never double-counted.

<p class="hint">{{hint}}</p>
<canvas id="cv" width="460" height="280"></canvas>
<div class="info">
  <span id="area-label">{{union_area_label}} <b id="area">0</b> {{px2}}</span>
  <span id="sum-label">{{sum_label}} <b id="sum">0</b> {{px2}}</span>
</div>
<div class="btns">
  <button id="add" type="button">{{btn_add}}</button>
  <button id="animate" type="button">{{btn_animate}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px;
         background: #f4f7fa; max-width: 100%; }
.info { display: flex; gap: 1.4rem; margin: .45rem 0 .5rem; font-size: .9rem; flex-wrap: wrap; }
#area { color: #0a7d33; }
#sum  { color: #555; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Watch how the covered area grows only when a new rectangle exposes fresh territory — a rectangle completely hidden inside an existing one contributes nothing. That is the key asymmetry: the sum of individual areas can be far larger than the union, and brute-force pixel counting would need far more work.

How hard is Klee's measure problem, really?

• Naïve inclusion-exclusion: with n rectangles there are up to $2^{n}$ subsets whose intersections you must account for. Hopeless for large n.
• Pixel counting: discretise the plane to a fine grid and mark each cell. Works, but the error depends on resolution and the runtime is proportional to the grid size, not n.
• The sweepline: sort all 2n vertical edges (left and right sides of each rectangle) by x-coordinate. Sweep a vertical line from left to right; each time it hits an edge, update a data structure that tracks which y-intervals are currently covered. The total area is the integral of the covered length over x. With a segment tree over the sorted y-coordinates the update takes $O(\log n)$ per event, giving $O(n \log n)$ overall.
• Lower bound: Fredman (1981) showed any comparison-based algorithm needs Ω(n log n) — so the sweepline is optimal in this model.
• Higher dimensions: in d dimensions the problem generalises to computing the volume of a union of boxes. The best algorithms run in $O(nᵈ/^{2})$ or O($n^{d-1}$ log n) depending on the approach. The 3-D case already requires careful work.

The sweepline idea is clean, provably optimal, and a blueprint for dozens of other geometry problems. It is one of the gems of computational geometry.

"What area do these regions jointly cover?" is a question that surfaces across computer science:

• VLSI and circuit layout: chip designers compute the total silicon area consumed by a set of wires or components, which are essentially unions of rectangles on a grid.
• Database query planning: the query optimiser in a relational database estimates how many rows a predicate will return. If two range conditions cover intervals on a continuous attribute, their union area is the relevant cardinality estimate.
• Computer graphics and rendering: shadow maps, light cones, and texture atlases all involve computing which portions of a canvas are covered by overlapping shapes.
• Collision detection: in 2-D game physics, detecting whether any two axis-aligned bounding boxes overlap is the rectangle-intersection cousin of Klee's problem.
• Spatial analytics: GIS tools compute the area of the union of administrative polygons or flood zones, often after approximating each polygon with a set of rectangles.

Understand the sweepline and you have a tool that powers geometry engines in databases, rendering pipelines, and chip-design tools alike. It connects naturally to the broader family of divide-and-conquer algorithms in geometry.

Klee's measure problem starts with a question a child could ask — how much table do my sticky notes cover? — and leads directly to one of the most beautiful ideas in algorithm design: the sweepline.

By reducing a 2-D area integral to a sequence of 1-D interval-coverage queries, the sweepline turns an apparent $2^{n}$ combinatorial explosion into a clean $O(n \log n)$ computation. Fredman's lower bound confirms there is no fundamentally better approach for comparison-based algorithms.

The lesson extends well beyond rectangles. Whenever a 2-D problem can be decomposed into a moving 1-D cross-section, the sweepline paradigm applies — and it does so with near-optimal efficiency. That is what makes Klee's measure problem a landmark not just in geometry, but in the art of algorithm design itself.