Largest empty rectangle

In computational geometry, the largest empty rectangle problem, maximal empty rectangle problem 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. The problems of this kind arise e.g., in electronic design automation, in design and verification of physical layout of integrated circuits. A maximal empty rectangle is a rectangle which is not contained in another empty rectangle. Each side of a maximal empty rectangle abuts an obstacle (otherwise the side may be shifted outwards, increasing the empty rectangle). An application of this kind is enumeration of "maximal white rectangles" in image segmentation R&D of image processing and pattern recognition. In the contexts of many algorithms for largest empty rectangles, "maximal empty rectangles" are candidate solutions to be considered by the algorithm, since it is easily proven that, e.g., a maximum-area empty rectangle is a maximal empty rectangle.

Classification 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

Maximum-area square The case when the sought rectangle is an axis-oriented square may be treated using Voronoi diagrams in L 1 {\displaystyle L_{1}} metrics for the corresponding obstacle set, similarly to the largest empty circle problem. In particular, for the case of points within rectangle an optimal algorithm of time complexity Θ ( n log ⁡ n ) {\displaystyle \Theta (n\log n)} is known.

Domain: rectangle containing points A problem first discussed 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 ) ) {\displaystyle O(\min(n^{2},s\log n))} , where s is the number of feasible solutions, i.e., maximal empty rectangles. They also proved that s = O ( n 2 ) {\displaystyle s=O(n^{2})} and gave an example in which s is quadratic in n. Afterwards a number of papers presented better algorithms for the problem.

Domain: line segment obstacles The problem of empty isothetic rectangles among isothetic line segments was first considered in 1990. Later a more general problem of empty isothetic rectangles among non-isothetic obstacles was considered.

Generalizations

Higher dimensions In 3-dimensional space, algorithms are known for finding a largest maximal empty isothetic cuboid problem, as well as for enumeration of all maximal isothetic empty cuboids.

See also Largest empty sphere Minimum bounding box, Minimum bounding rectangle

References