Skip to content

Foundations

Jump to bottom
Wolren edited this page Apr 30, 2026 · 5 revisions

Geometric Foundations

Background on the Largest Inscribed Rectangle problem and the geometric principles underlying LIRiAP algorithms.

Problem Definition

Given a simple polygon $P$ (possibly with holes), find the rectangle $R$ of maximum area such that $R$ is strictly contained in $P$. The rectangle may be rotated (non-axis-aligned).

Variants

  1. Axis-aligned: Rectangle sides parallel to coordinate axes
  2. Rotated: Rectangle may have any orientation
  3. With constraints: Maximum aspect ratio, minimum area, etc.

Theoretical Background

Axis-Aligned Case

For axis-aligned rectangles, Daniels et al. (1997) proved that the optimal rectangle always has at least two sides determined by vertex coordinates of the polygon. This enables efficient exact solvers using vertex-coordinate grids.

Rotated Case

The general (rotated) case is NP-hard to solve exactly. Approaches include:

  • Heuristic search over orientation space
  • Grid-based approximation
  • Boundary-coordinate raster methods (BCRS)

Key Algorithms and References

Largest Rectangle in Histogram (LRH)

The classic stack-based algorithm for finding the largest rectangle in a histogram. Runs in O(n) time.

Reference: Klingel, E. (1986). Finding the largest rectangle in a polygon. Algorithmica.

Alt/Amenta (Convex Polygons)

For convex polygons, the optimal axis-aligned rectangle has its top and bottom edges tangent at polygon vertices. This enables O(n²) exact solving via vertex-pair enumeration.

References:

Daniels et al. (General Polygons)

Core Theorem: The largest axis-aligned rectangle in a simple polygon always has at least two sides determined by vertex x- or y-coordinates. This is the foundation for the exact axis-aligned solvers.

Reference: Daniels, K., Milenkovic, V., Roth, D. (1997). Finding the largest axis-aligned rectangle in a polygon. Proc. 13th Canadian Conf. Computational Geometry.

Brent Optimization

Bounded scalar optimization for angle refinement. Used for local search around candidate orientations.

Reference: Brent, R.P. (1973). Algorithms for Finding Zeros and Extrema of Functions Without Calculating Derivatives. Prentice-Hall.

Computational Geometry Foundations

References:

  • [1] Bentley, J.L. (1977). Programming Pearls: Fast Algorithms for Polygon Containment. Communications of the ACM, 20(11), 887-891. https://dl.acm.org/doi/10.1145/1283920.3283334
  • [2] Preparata, F.P., & Shamos, M.I. (1985). Computational Geometry: An Introduction. Springer-Verlag.

Novel Contributions in LIRiAP

BCRS: Vertex-Coordinate Grid + Variable-Pitch LRH

The BCRS algorithm combines vertex-coordinate grid construction with a variable-pitch variant of the Largest Rectangle in Histogram algorithm to guarantee finding the global optimum for rotated rectangles.

Grid Construction

Let $V_x = {x_i}$ be the set of unique x-coordinates from all polygon vertices (exterior and interior rings), augmented with the polygon's bounding box limits $\text{minx}$ and $\text{maxx}$. Similarly, construct $V_y = {y_j}$ from y-coordinates.

The resulting grid has dimensions $|V_x| - 1$ columns by $|V_y| - 1$ rows. The cell at row $j$, column $i$ spans $[V_x[i], V_x[i+1]] \times [V_y[j], V_y[j+1]]$.

If $|V_x| > 300$ or $|V_y| > 300$, the vertex-coordinate grid becomes too fine, and the algorithm falls back to a coarser uniform grid for the initial seed.

Occupancy Mask

Define the occupancy mask $M_{ij} \in {0, 1}$ where $M_{ij} = 1$ if the cell center $((V_x[i] + V_x[i+1])/2, (V_y[j] + V_y[j+1])/2)$ lies inside the polygon, and 0 otherwise.

Variable-Pitch LRH

For each row $j$, compute the height array $H_i^j = \sum_{k=0}^{j} M_{ik}$ representing cumulative occupancy from the top. Apply the stack-based LRH algorithm where the width of each span uses variable pitch:

$$\text{width}(i_{\text{start}}, i_{\text{end}}) = V_x[i_{\text{end}} + 1] - V_x[i_{\text{start}}]$$

rather than uniform grid spacing. The depth is:

$$\text{depth}(j, h) = V_y[j+1] - V_y[j-h+1]$$

The area of each candidate rectangle is $\text{width} \times \text{depth}$. This variable-pitch approach exploits the Daniels et al. theorem while accounting for non-uniform vertex spacing.

Optimality Guarantee

Theorem (Daniels et al., 1997): The largest axis-aligned rectangle in a simple polygon has at least two sides aligned with vertex x- or y-coordinates.

Corollary: Searching the vertex-coordinate grid $V_x \times V_y$ finds the global optimum for axis-aligned rectangles within the polygon.

SDF-Guided Boundary Expansion

After obtaining an initial axis-aligned rectangle seed, SDF-guided expansion tightens the rectangle against the polygon boundary by computing the exact distance to the boundary at each side.

Signed Distance Field Definition

Define the signed distance field $\phi: \mathbb{R}^2 \to \mathbb{R}$ as:

$$\phi(p) = \begin{cases} \text{dist}(p, \partial P) & \text{if } p \notin P \\ -\text{dist}(p, \partial P) & \text{if } p \in P \end{cases}$$

where $\text{dist}(p, \partial P)$ is the Euclidean distance from point $p$ to the polygon boundary. For points inside $P$, we compute the distance to the nearest boundary (exterior ring or any hole).

The SDF provides the exact distance to the polygon boundary, independent of vertex coordinates.

Expansion Bound Computation

Consider expanding the left side of rectangle $R = [x_0, x_1] \times [y_0, y_1]$ by distance $d$. Let $m = (x_0, (y_0 + y_1)/2)$ be the midpoint of the left edge.

Evaluate $s = \phi(m)$:

  • If $s < 0$ (midpoint is inside), the expansion is bounded by both the polygon edge and the bounding box:

    $$d_{\text{max}} = \min(x_0 - \text{minx}, |s|)$$

  • If $s \geq 0$ (midpoint is outside), expansion is bounded only by the bounding box:

    $$d_{\text{max}} = x_0 - \text{minx}$$

This bound uses the actual distance to the boundary $|s|$, not an approximation from vertex-coordinate gaps.

Binary Search Refinement

To find the maximum expansion distance maintaining containment, perform binary search over $d \in [0, d_{\text{max}}]$:

$$d^* = \max { d \in [0, d_{\text{max}}] : P \supseteq [x_0 - d, x_1] \times [y_0, y_1] }$$

The binary search evaluates containment at each step using the polygon boundary representation (10 iterations provides sufficient precision).

Repeat this process for all four sides (left, right, bottom, top). Run three iterations of coordinate ascent to jointly optimize all sides simultaneously, as expanding one side may enable further expansion on others.

SDF-Based Containment Certification

After expansion, verify strict containment using the SDF.

Maximum SDF Evaluation

Compute the maximum SDF value over the rectangle interior:

$$\phi_{\text{max}} = \max_{p \in R} \phi(p)$$

Since the SDF is continuous and the rectangle is convex, the maximum occurs at one of the boundary points. We sample the four corners and the midpoints of each edge (eight samples total):

$$\phi_{\text{max}} \approx \max { \phi(c_i) : i = 1,\ldots,8 }$$

This is O(1) with respect to polygon size.

Certification Decision

  • If $\phi_{\text{max}} \leq \epsilon$ (where $\epsilon = 10^{-7}$), the rectangle is certified as strictly contained.

  • Otherwise, apply symmetric shrinkage by $\delta = \phi_{\text{max}} + 2\epsilon$:

    $$R' = R \oplus (-\delta)$$

    where $\oplus$ denotes Minkowski subtraction (shrink by $\delta$ on all sides).

  • If $\delta > 0.2 \times \min(\text{width}, \text{height}) / 2$, reject the rectangle (excessive shrinkage).

  • Otherwise, re-verify $\phi_{\text{max}} \leq \epsilon$ on $R'$. If it passes, return the shrunk rectangle; otherwise, reject.

The shrink distance $\delta$ guarantees containment because all interior points are at least $\phi_{\text{max}}$ from the boundary, and shrinking by $\phi_{\text{max}} + 2\epsilon$ ensures a safety margin.

Navigation

Getting Started

Algorithms

Theory

Performance

Reference

Clone this wiki locally