Where Klee's Measure Problem Matters

Introduction

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.

Try It

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">Click <b>Add rectangle</b> to place a random rectangle. The sweepline (dashed line) scans left→right and tallies the union area — overlaps are never double-counted.</p>
<canvas id="cv" width="460" height="280"></canvas>
<div class="info">
  <span id="area-label">Union area: <b id="area">0</b> px²</span>
  <span id="sum-label">Sum of areas: <b id="sum">0</b> px²</span>
</div>
<div class="btns">
  <button id="add" type="button">Add rectangle</button>
  <button id="animate" type="button">Animate sweepline</button>
  <button id="reset" type="button" class="ghost">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; }

// Klee's measure problem: compute the area of the union of axis-aligned rectangles.
// Algorithm: coordinate-compress the y-values, sweep vertical events (left/right
// edges), maintain an interval-coverage count, integrate covered length over x.
// Time O(n^2) here for clarity (n small); O(n log n) with a segment tree.

const cv  = document.getElementById('cv');
const ctx = cv.getContext('2d');
const W = cv.width, H = cv.height;
const PAD = 20; // canvas padding

// Palette of semi-transparent fill colors
const COLORS = [
  'rgba(29,53,87,0.25)','rgba(230,57,70,0.25)','rgba(10,125,51,0.25)',
  'rgba(150,100,200,0.25)','rgba(200,130,0,0.25)','rgba(0,150,180,0.25)'
];

let rects = []; // {x1,y1,x2,y2,color} in canvas coords

// ── Core algorithm: union area via sweepline ───────────────────────────────────────────
function unionArea(rects) {
  if (!rects.length) return 0;
  // Collect all unique x-coordinates (events)
  const xs = [];
  rects.forEach(r => { xs.push(r.x1); xs.push(r.x2); });
  xs.sort((a, b) => a - b);
  // Remove duplicates
  const uxs = [...new Set(xs)];
  let area = 0;
  for (let i = 0; i < uxs.length - 1; i++) {
    const xL = uxs[i], xR = uxs[i + 1];
    const xMid = (xL + xR) / 2;
    // Which rectangles cover xMid?
    const active = rects.filter(r => r.x1 <= xMid && xMid <= r.x2);
    // Compute covered y-length (union of y-intervals)
    area += (xR - xL) * coveredLength(active);
  }
  return area;
}

// Covered length of union of 1-D intervals [r.y1, r.y2]
function coveredLength(active) {
  if (!active.length) return 0;
  const intervals = active.map(r => [Math.min(r.y1,r.y2), Math.max(r.y1,r.y2)]);
  intervals.sort((a, b) => a[0] - b[0]);
  let total = 0, cur = intervals[0];
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] <= cur[1]) {
      cur = [cur[0], Math.max(cur[1], intervals[i][1])];
    } else {
      total += cur[1] - cur[0];
      cur = intervals[i];
    }
  }
  total += cur[1] - cur[0];
  return total;
}

// ── Drawing ────────────────────────────────────────────────────────────────────────────
function draw(sweepX) {
  ctx.clearRect(0, 0, W, H);

  // Shade union region (scan strips between sorted x-events)
  if (rects.length) {
    const xs = [];
    rects.forEach(r => { xs.push(r.x1); xs.push(r.x2); });
    xs.sort((a, b) => a - b);
    const uxs = [...new Set(xs)];
    ctx.fillStyle = 'rgba(10,125,51,0.10)';
    for (let i = 0; i < uxs.length - 1; i++) {
      const xL = uxs[i], xR = uxs[i + 1];
      const xMid = (xL + xR) / 2;
      const active = rects.filter(r => r.x1 <= xMid && xMid <= r.x2);
      const intervals = active.map(r => [Math.min(r.y1,r.y2), Math.max(r.y1,r.y2)]);
      intervals.sort((a, b) => a[0] - b[0]);
      let cur = null;
      for (const iv of intervals) {
        if (!cur) { cur = [...iv]; continue; }
        if (iv[0] <= cur[1]) cur[1] = Math.max(cur[1], iv[1]);
        else { ctx.fillRect(xL, cur[0], xR - xL, cur[1] - cur[0]); cur = [...iv]; }
      }
      if (cur) ctx.fillRect(xL, cur[0], xR - xL, cur[1] - cur[0]);
    }
  }

  // Draw each rectangle
  rects.forEach(r => {
    ctx.fillStyle = r.color;
    ctx.fillRect(r.x1, r.y1, r.x2 - r.x1, r.y2 - r.y1);
    ctx.strokeStyle = r.color.replace('0.25', '0.9');
    ctx.lineWidth = 1.5;
    ctx.strokeRect(r.x1, r.y1, r.x2 - r.x1, r.y2 - r.y1);
  });

  // Draw sweepline
  if (sweepX !== undefined) {
    ctx.save();
    ctx.setLineDash([6, 4]);
    ctx.strokeStyle = '#e63946';
    ctx.lineWidth = 2;
    ctx.beginPath(); ctx.moveTo(sweepX, 0); ctx.lineTo(sweepX, H); ctx.stroke();
    ctx.restore();
  }
}

function updateLabels() {
  const ua = unionArea(rects);
  const sa = rects.reduce((s, r) => s + Math.abs((r.x2-r.x1)*(r.y2-r.y1)), 0);
  document.getElementById('area').textContent = Math.round(ua).toLocaleString();
  document.getElementById('sum').textContent  = Math.round(sa).toLocaleString();
}

function randInt(lo, hi) { return Math.floor(Math.random() * (hi - lo + 1)) + lo; }

document.getElementById('add').addEventListener('click', () => {
  const w = randInt(50, 160), h = randInt(40, 120);
  const x1 = randInt(PAD, W - PAD - w), y1 = randInt(PAD, H - PAD - h);
  rects.push({ x1, y1, x2: x1 + w, y2: y1 + h,
               color: COLORS[rects.length % COLORS.length] });
  draw();
  updateLabels();
});

let animId = null;
document.getElementById('animate').addEventListener('click', () => {
  if (animId) { cancelAnimationFrame(animId); animId = null; draw(); return; }
  let x = PAD;
  function step() {
    draw(x);
    x += 2;
    if (x > W - PAD) { draw(); animId = null; return; }
    animId = requestAnimationFrame(step);
  }
  step();
});

document.getElementById('reset').addEventListener('click', () => {
  if (animId) { cancelAnimationFrame(animId); animId = null; }
  rects = [];
  draw();
  document.getElementById('area').textContent = '0';
  document.getElementById('sum').textContent  = '0';
});

draw();
console.log('Klee measure demo ready. unionArea test:');
// Quick self-test: two 10x10 squares, second offset by 5 → union = 175
const test = [
  {x1:0,y1:0,x2:10,y2:10},{x1:5,y1:0,x2:15,y2:10}
];
const result = unionArea(test);
console.log('Expected 150, got', result, result === 150 ? 'PASS' : 'FAIL');

<p class="hint">Click <b>Add rectangle</b> to place a random rectangle. The sweepline (dashed line) scans left→right and tallies the union area — overlaps are never double-counted.</p>
<canvas id="cv" width="460" height="280"></canvas>
<div class="info">
  <span id="area-label">Union area: <b id="area">0</b> px²</span>
  <span id="sum-label">Sum of areas: <b id="sum">0</b> px²</span>
</div>
<div class="btns">
  <button id="add" type="button">Add rectangle</button>
  <button id="animate" type="button">Animate sweepline</button>
  <button id="reset" type="button" class="ghost">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; }

// Klee's measure problem: compute the area of the union of axis-aligned rectangles.
// Algorithm: coordinate-compress the y-values, sweep vertical events (left/right
// edges), maintain an interval-coverage count, integrate covered length over x.
// Time O(n^2) here for clarity (n small); O(n log n) with a segment tree.

const cv  = document.getElementById('cv');
const ctx = cv.getContext('2d');
const W = cv.width, H = cv.height;
const PAD = 20; // canvas padding

// Palette of semi-transparent fill colors
const COLORS = [
  'rgba(29,53,87,0.25)','rgba(230,57,70,0.25)','rgba(10,125,51,0.25)',
  'rgba(150,100,200,0.25)','rgba(200,130,0,0.25)','rgba(0,150,180,0.25)'
];

let rects = []; // {x1,y1,x2,y2,color} in canvas coords

// ── Core algorithm: union area via sweepline ───────────────────────────────────────────
function unionArea(rects) {
  if (!rects.length) return 0;
  // Collect all unique x-coordinates (events)
  const xs = [];
  rects.forEach(r => { xs.push(r.x1); xs.push(r.x2); });
  xs.sort((a, b) => a - b);
  // Remove duplicates
  const uxs = [...new Set(xs)];
  let area = 0;
  for (let i = 0; i < uxs.length - 1; i++) {
    const xL = uxs[i], xR = uxs[i + 1];
    const xMid = (xL + xR) / 2;
    // Which rectangles cover xMid?
    const active = rects.filter(r => r.x1 <= xMid && xMid <= r.x2);
    // Compute covered y-length (union of y-intervals)
    area += (xR - xL) * coveredLength(active);
  }
  return area;
}

// Covered length of union of 1-D intervals [r.y1, r.y2]
function coveredLength(active) {
  if (!active.length) return 0;
  const intervals = active.map(r => [Math.min(r.y1,r.y2), Math.max(r.y1,r.y2)]);
  intervals.sort((a, b) => a[0] - b[0]);
  let total = 0, cur = intervals[0];
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] <= cur[1]) {
      cur = [cur[0], Math.max(cur[1], intervals[i][1])];
    } else {
      total += cur[1] - cur[0];
      cur = intervals[i];
    }
  }
  total += cur[1] - cur[0];
  return total;
}

// ── Drawing ────────────────────────────────────────────────────────────────────────────
function draw(sweepX) {
  ctx.clearRect(0, 0, W, H);

  // Shade union region (scan strips between sorted x-events)
  if (rects.length) {
    const xs = [];
    rects.forEach(r => { xs.push(r.x1); xs.push(r.x2); });
    xs.sort((a, b) => a - b);
    const uxs = [...new Set(xs)];
    ctx.fillStyle = 'rgba(10,125,51,0.10)';
    for (let i = 0; i < uxs.length - 1; i++) {
      const xL = uxs[i], xR = uxs[i + 1];
      const xMid = (xL + xR) / 2;
      const active = rects.filter(r => r.x1 <= xMid && xMid <= r.x2);
      const intervals = active.map(r => [Math.min(r.y1,r.y2), Math.max(r.y1,r.y2)]);
      intervals.sort((a, b) => a[0] - b[0]);
      let cur = null;
      for (const iv of intervals) {
        if (!cur) { cur = [...iv]; continue; }
        if (iv[0] <= cur[1]) cur[1] = Math.max(cur[1], iv[1]);
        else { ctx.fillRect(xL, cur[0], xR - xL, cur[1] - cur[0]); cur = [...iv]; }
      }
      if (cur) ctx.fillRect(xL, cur[0], xR - xL, cur[1] - cur[0]);
    }
  }

  // Draw each rectangle
  rects.forEach(r => {
    ctx.fillStyle = r.color;
    ctx.fillRect(r.x1, r.y1, r.x2 - r.x1, r.y2 - r.y1);
    ctx.strokeStyle = r.color.replace('0.25', '0.9');
    ctx.lineWidth = 1.5;
    ctx.strokeRect(r.x1, r.y1, r.x2 - r.x1, r.y2 - r.y1);
  });

  // Draw sweepline
  if (sweepX !== undefined) {
    ctx.save();
    ctx.setLineDash([6, 4]);
    ctx.strokeStyle = '#e63946';
    ctx.lineWidth = 2;
    ctx.beginPath(); ctx.moveTo(sweepX, 0); ctx.lineTo(sweepX, H); ctx.stroke();
    ctx.restore();
  }
}

function updateLabels() {
  const ua = unionArea(rects);
  const sa = rects.reduce((s, r) => s + Math.abs((r.x2-r.x1)*(r.y2-r.y1)), 0);
  document.getElementById('area').textContent = Math.round(ua).toLocaleString();
  document.getElementById('sum').textContent  = Math.round(sa).toLocaleString();
}

function randInt(lo, hi) { return Math.floor(Math.random() * (hi - lo + 1)) + lo; }

document.getElementById('add').addEventListener('click', () => {
  const w = randInt(50, 160), h = randInt(40, 120);
  const x1 = randInt(PAD, W - PAD - w), y1 = randInt(PAD, H - PAD - h);
  rects.push({ x1, y1, x2: x1 + w, y2: y1 + h,
               color: COLORS[rects.length % COLORS.length] });
  draw();
  updateLabels();
});

let animId = null;
document.getElementById('animate').addEventListener('click', () => {
  if (animId) { cancelAnimationFrame(animId); animId = null; draw(); return; }
  let x = PAD;
  function step() {
    draw(x);
    x += 2;
    if (x > W - PAD) { draw(); animId = null; return; }
    animId = requestAnimationFrame(step);
  }
  step();
});

document.getElementById('reset').addEventListener('click', () => {
  if (animId) { cancelAnimationFrame(animId); animId = null; }
  rects = [];
  draw();
  document.getElementById('area').textContent = '0';
  document.getElementById('sum').textContent  = '0';
});

draw();
console.log('Klee measure demo ready. unionArea test:');
// Quick self-test: two 10x10 squares, second offset by 5 → union = 175
const test = [
  {x1:0,y1:0,x2:10,y2:10},{x1:5,y1:0,x2:15,y2:10}
];
const result = unionArea(test);
console.log('Expected 150, got', result, result === 150 ? 'PASS' : 'FAIL');

Result

Console

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.

The Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Comments

Loading comments...

https://www.kipuhub.com/en/article/klees-measure/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Klee's Measure Problem

When a simple area question demands a clever algorithm