The Largest Empty Rectangle

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

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">{{hint}}</p>
<canvas id="cvs" width="480" height="320"></canvas>
<div class="info" id="info">{{add_points}}</div>
<div class="btns">
  <button id="btnRandom" type="button">{{btn_random}}</button>
  <button id="btnClear" 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: 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; }

// Code not found

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.

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(n^{2})$ vertical pairs × $O(n^{2})$ horizontal pairs = $O(n^{4})$ candidates. Checking each takes $O(n)$ time, so brute force is $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(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)$ using a stack — a classic trick.
• Sweeping all n possible bottom edges costs $O(n)$ each → $O(n^{2})$ total. A more refined approach with fractional cascading brings this to $O(n \log ^{2}n)$, and the current best is $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.

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(n \log n)$ algorithm is fast enough to run interactively, making real-time layout and planning tools possible.

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.