Introduction

Imagine scattering a handful of nails on a table and then asking: what is the largest rectangular tray you can slide onto the table without hitting any nail? The tray must be axis-aligned — no tilting — but its position and size are yours to choose.

This is the Largest Empty Rectangle (LER) problem. Given n points in the plane, find the axis-aligned rectangle of maximum area that contains none of them, yet fits inside some bounding box.

It sounds like a simple visual exercise, but a naive search over all possible rectangles is enormous. What makes the problem interesting — and useful — is that the answer can be found in O(nlog⁡n)O(n \log n) time, a fact that takes genuine algorithmic insight to achieve.

From page layout and ad placement to gap detection in sensor data, the largest empty rectangle quietly powers dozens of real systems. And its proof technique — the histogram sweep — is one of the most elegant tools in computational geometry.

Try It

Click anywhere on the canvas to place points. The algorithm instantly recomputes and highlights the largest empty axis-aligned rectangle — the biggest clear region that avoids every point you placed.

<p class="hint">Click on the canvas to place points. The highlighted rectangle is the <b>largest empty axis-aligned rectangle</b> — the biggest clear region that avoids every point. Drag points to move them.</p>
<canvas id="cvs" width="480" height="320"></canvas>
<div class="info" id="info">Add points to see the largest empty rectangle.</div>
<div class="btns">
  <button id="btnRandom" type="button">Random points</button>
  <button id="btnClear" 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: 1.5px solid #cdd9e3; border-radius: 8px;
         cursor: crosshair; max-width: 100%; background: #f7f9fb; }
.info { font-size: .95rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; color: #1d3557; }
.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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Largest Empty Rectangle (LER) demo.
//
// Key structural fact (Chazelle, Drysdale & Lee 1986): the optimal axis-aligned
// empty rectangle has every side touching either the bounding box or a point.
// So we only need x-coordinates and y-coordinates drawn from the point set plus
//
// Algorithm (O(n^3) for the demo — fast enough for up to ~30 points):
//   For each adjacent pair of x-boundaries (lx, rx):
//     Mark each y-band [ys[k], ys[k+1]] as blocked if any point lies strictly
//     inside (lx, rx) at that y.
//     Find the largest contiguous run of unblocked bands; within each run,
//   Track the global best.

const W = 480, H = 320, PAD = 20, R = 6;
const cvs = document.getElementById('cvs');
const ctx = cvs.getContext('2d');
let pts = [];
let bestRect = null;
let dragging = -1;

const BX1 = PAD, BY1 = PAD, BX2 = W - PAD, BY2 = H - PAD;

function computeLER(points) {
  if (!points.length) return { x1: BX1, y1: BY1, x2: BX2, y2: BY2, area: (BX2-BX1)*(BY2-BY1) };

  const xs = [...new Set([BX1, BX2, ...points.map(p => p.x)])].sort((a, b) => a - b);
  const ys = [...new Set([BY1, BY2, ...points.map(p => p.y)])].sort((a, b) => a - b);
  const ny = ys.length - 1;

  let best = { x1: BX1, y1: BY1, x2: BX2, y2: BY1, area: 0 };

  for (let i = 0; i < xs.length - 1; i++) {
    const lx = xs[i], rx = xs[i + 1];

    // Determine which y-bands are blocked by points strictly inside this x-strip.
    const blocked = new Array(ny).fill(false);
    for (const p of points) {
      if (p.x > lx && p.x < rx) {
        for (let k = 0; k < ny; k++) {
          if (p.y >= ys[k] && p.y <= ys[k + 1]) blocked[k] = true;
        }
      }
    }

    // Band heights (0 if blocked).
    const bh = blocked.map((b, k) => b ? 0 : ys[k + 1] - ys[k]);

    // Scan contiguous runs of free bands; try every sub-range within each run.
    // The area is always (rx-lx)*(ys[b+1]-ys[a]) for sub-range [a..b].
    let runStart = -1;
    for (let k = 0; k <= ny; k++) {
      const h = k < ny ? bh[k] : 0;
      if (h === 0) {
        if (runStart >= 0) {
          // Evaluate all sub-ranges [runStart..k-1]
          for (let a = runStart; a < k; a++) {
            for (let b = a; b < k; b++) {
              const area = (rx - lx) * (ys[b + 1] - ys[a]);
              if (area > best.area) {
                best = { x1: lx, y1: ys[a], x2: rx, y2: ys[b + 1], area };
              }
            }
          }
        }
        runStart = -1;
      } else {
        if (runStart < 0) runStart = k;
      }
    }
    // Flush a run that reaches the end of the band array.
    if (runStart >= 0) {
      const k = ny;
      for (let a = runStart; a < k; a++) {
        for (let b = a; b < k; b++) {
          const area = (rx - lx) * (ys[b + 1] - ys[a]);
          if (area > best.area) {
            best = { x1: lx, y1: ys[a], x2: rx, y2: ys[b + 1], area };
          }
        }
      }
    }
  }
  return best;
}

function draw() {
  ctx.clearRect(0, 0, W, H);

  // Bounding box outline
  ctx.strokeStyle = '#bcc8d4';
  ctx.lineWidth = 1;
  ctx.strokeRect(BX1, BY1, BX2 - BX1, BY2 - BY1);

  // Largest empty rectangle
  if (bestRect) {
    const { x1, y1, x2, y2 } = bestRect;
    ctx.fillStyle = 'rgba(29,53,87,0.12)';
    ctx.fillRect(x1, y1, x2 - x1, y2 - y1);
    ctx.strokeStyle = '#1d3557';
    ctx.lineWidth = 2;
    ctx.strokeRect(x1, y1, x2 - x1, y2 - y1);
    document.getElementById('info').textContent =
      fmt('Largest empty rectangle: %round% × %round2% px  (area %round3% px²)', { round: Math.round(x2 - x1), round2: Math.round(y2 - y1), round3: Math.round(bestRect.area) });
  } else {
    document.getElementById('info').textContent =
      pts.length ? 'Computing…' : 'Add points to see the largest empty rectangle.';
  }

  // Points
  for (let i = 0; i < pts.length; i++) {
    ctx.beginPath();
    ctx.arc(pts[i].x, pts[i].y, R, 0, 2 * Math.PI);
    ctx.fillStyle = '#e63946';
    ctx.fill();
    ctx.strokeStyle = '#fff';
    ctx.lineWidth = 1.5;
    ctx.stroke();
  }
}

function update() {
  bestRect = computeLER(pts);
  draw();
}

function clamp(v, lo, hi) { return Math.max(lo, Math.min(hi, v)); }

function hitPt(x, y) {
  for (let i = pts.length - 1; i >= 0; i--) {
    const dx = pts[i].x - x, dy = pts[i].y - y;
    if (dx * dx + dy * dy <= R * R * 3) return i;
  }
  return -1;
}

function canvasPos(e, touch) {
  const r = cvs.getBoundingClientRect();
  const sx = W / r.width, sy = H / r.height;
  const src = touch || e;
  return {
    x: clamp((src.clientX - r.left) * sx, BX1, BX2),
    y: clamp((src.clientY - r.top) * sy, BY1, BY2)
  };
}

cvs.addEventListener('mousedown', e => {
  const { x, y } = canvasPos(e);
  const hit = hitPt(x, y);
  if (hit >= 0) { dragging = hit; return; }
  pts.push({ x, y });
  update();
});
cvs.addEventListener('mousemove', e => {
  if (dragging < 0) return;
  const { x, y } = canvasPos(e);
  pts[dragging].x = x; pts[dragging].y = y;
  update();
});
cvs.addEventListener('mouseup', () => { dragging = -1; });
cvs.addEventListener('mouseleave', () => { dragging = -1; });

cvs.addEventListener('touchstart', e => {
  e.preventDefault();
  const { x, y } = canvasPos(e, e.touches[0]);
  const hit = hitPt(x, y);
  if (hit >= 0) { dragging = hit; return; }
  pts.push({ x, y });
  update();
}, { passive: false });
cvs.addEventListener('touchmove', e => {
  e.preventDefault();
  if (dragging < 0) return;
  const { x, y } = canvasPos(e, e.touches[0]);
  pts[dragging].x = x; pts[dragging].y = y;
  update();
}, { passive: false });
cvs.addEventListener('touchend', () => { dragging = -1; });

document.getElementById('btnRandom').addEventListener('click', () => {
  const n = 8 + Math.floor(Math.random() * 7);
  pts = Array.from({ length: n }, () => ({
    x: BX1 + Math.random() * (BX2 - BX1),
    y: BY1 + Math.random() * (BY2 - BY1)
  }));
  update();
});
document.getElementById('btnClear').addEventListener('click', () => {
  pts = []; bestRect = null; draw();
});

// Initial example
pts = [
  { x: 160, y: 100 }, { x: 340, y: 90 },  { x: 260, y: 200 },
  { x: 120, y: 230 }, { x: 400, y: 260 },  { x: 220, y: 140 }
];
update();

// Self-test (runs silently in console)
(function selfTest() {
  // Test: center point splits canvas; each half-width strip has full height
  const cx = (BX1 + BX2) / 2;
  const r = computeLER([{ x: cx, y: (BY1 + BY2) / 2 }]);
  const expectedArea = Math.max((cx - BX1) * (BY2 - BY1), (BX2 - cx) * (BY2 - BY1));
  console.assert(r.area === expectedArea, 'Self-test failed: area mismatch');
  // Test: no points -> whole box
  const r2 = computeLER([]);
  console.assert(r2.area === (BX2 - BX1) * (BY2 - BY1), 'Self-test failed: empty case');
  console.log('LER self-test passed. center-point area:', r.area, 'empty area:', r2.area);
})();
Result
Console

Notice how the optimal rectangle always has at least one edge flush against a point (or the boundary). Moving a single point can cause the solution to jump to an entirely different region. Add many points and watch the gaps shrink — yet the algorithm always finds the largest one without searching every possible rectangle.

The Real Complexity

How many candidate rectangles are there? A naive bound: the two vertical sides can each coincide with a point's x-coordinate (or the boundary), and likewise for the horizontal sides — giving O(n2)O(n^{2}) vertical pairs × O(n2)O(n^{2}) horizontal pairs = O(n4)O(n^{4}) candidates. Checking each takes O(n)O(n) time, so brute force is O(n5)O(n^{5}). Hopeless.

The key structural insight, proved by Chazelle, Drysdale, and Lee (1986), is that the optimal rectangle is maximal — it is blocked on every side by either a point or the bounding box. This means:

  • Every side can be charged to a specific point or boundary edge, reducing the search to O(n2)O(n^{2}) candidates.
  • A sweep-line + histogram technique processes these candidates cleverly: fix the bottom edge, sweep upward, and for each row maintain a histogram of heights to the nearest point above. The largest rectangle in a histogram can be found in O(n)O(n) using a stack — a classic trick.
  • Sweeping all n possible bottom edges costs O(n)O(n) each → O(n2)O(n^{2}) total. A more refined approach with fractional cascading brings this to O(nlog⁡2n)O(n \log ^{2}n), and the current best is O(nlog⁡n)O(n \log n).

The problem is solved — there is an optimal polynomial-time algorithm. It is not NP-hard. It belongs to the world of classical computational geometry where clever data structures turn what looks like a huge search into an efficient scan. Compare this to the combinatorial difficulty of P vs NP, where no such shortcut is known to exist.

Where It Matters

The largest empty rectangle is one of those problems that looks academic until you realize how many systems quietly depend on finding the biggest clear region:

  • Page layout and ad placement: given fixed text blocks and images, where does the largest open rectangle fit for a new ad or image? Publishers use variants of LER to place content without overlap.
  • Map labeling: geographic information systems must place labels without covering cities or roads. The largest empty space near each feature is a natural target — see also related work on closest pair as a building block.
  • Sensor data gaps: in a time-series heatmap, the LER identifies the longest uninterrupted gap — useful for anomaly detection and quality control.
  • Free-space in robotics: given a 2D occupancy grid of obstacles, the LER finds the largest rectangular corridor a robot can traverse without collision.
  • VLSI floor planning: chip designers pack rectangular components onto a die. Finding the biggest remaining empty rectangle guides where the next component can go.

In each case the O(nlog⁡n)O(n \log n) algorithm is fast enough to run interactively, making real-time layout and planning tools possible.

Conclusion

The largest empty rectangle is a satisfying story in computational geometry: a search space that naively has quadrillions of candidates collapses, through one structural observation, into an algorithm that runs in near-linear time.

The key insight — that the optimal rectangle is always flush against some point or boundary — is the kind of fact that looks obvious in hindsight but requires a proof. Once you have it, a sweep-line and a stack do the rest.

Not every geometric search problem yields so cleanly. Some relatives — like the largest empty convex region, or the three-dimensional analogue — remain open or have worse bounds. But the axis-aligned rectangle version is a gem: elegant, fast, and quietly essential to the systems that lay out pages, plan routes, and find gaps in data. A reminder that asking "where is the biggest empty space?" is never a trivial question — but sometimes the answer is beautifully efficient.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/largest-empty-rectangle/Content licensed under CC BY-NC 4.0.