Largest empty rectangle

In computational geometry, the largest empty rectangle, LER, maximal empty rectangle, MER, or maximum empty rectangle problem is the problem of finding a rectangle of maximal size to be placed among obstacles in the plane. There are a number of variants of the problem, depending on the particularities of this generic formulation, in particular, depending on the measure of the "size", domain (type of obstacles), and the orientation of the rectangle.

In terms of size measure, the two most common cases are the largest-area empty rectangle and largest-perimeter empty rectangle.

Another major classification is whether the rectangle is sought among axis-oriented or arbitrarily oriented rectangles.

Special cases

Minimum-area square

The case when the sought rectangle is an axis-oriented square may be treated using Voronoi diagrams in $L_{1}$metrics for the corresponding obstacle set. In particular, for the case of points within rectangle an optimal algorithm of time complexity $\Theta (n\,\log \,n)$ is known.

Domain: rectangle containing points

A problem first discused by Naamad, Lee and Hsu in 1983 is stated as follows: given a rectangle A containing n points, find a largest-area rectangle with sides parallel to those of A which lies within A and does not contain any of the given points. Naamad, Lee and Hsu presented an algorithm of time complexity $O(min(n^{2},s\,\log \,n))$, where s is the number of feasible solutions, i.e., empty rectangles all four sides of which either contain an obstacle point or lie on a side of A. They also proved that $s=O(n^{2})$ and gave an example in which s is quadratic in n. Afterwards a umber of papers presented better algorithms for the problem.