Largest empty rectangle

Last updated August 08, 2023

In computational geometry, the largest empty rectangle problem,^[2]maximal empty rectangle problem^[3] or maximum empty rectangle problem,^[4] 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.

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.^[6] 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.^[7]

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}$ 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 $\Theta (n\log n)$ is known.^[8]

Domain: rectangle containing points

A problem first discussed by Naamad, Lee and Hsu in 1983^[1] 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., maximal empty rectangles. They also proved that $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^[9] in 1990.^[10] Later a more general problem of empty isothetic rectangles among non-isothetic obstacles was considered.^[9]

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.^[11]

Related Research Articles

In computational complexity theory, the class NC (for "Nick's Class") is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. In other words, a problem with input size n is in NC if there exist constants c and k such that it can be solved in time $O ((log n) c)$ using $O (n k)$ parallel processors. Stephen Cook coined the name "Nick's class" after Nick Pippenger, who had done extensive research on circuits with polylogarithmic depth and polynomial size.

In computer science, the clique problem is the computational problem of finding cliques in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a maximum clique, finding a maximum weight clique in a weighted graph, listing all maximal cliques, and solving the decision problem of testing whether a graph contains a clique larger than a given size.

In the mathematical area of graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph $is an induced subgraph of that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.$

In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set $of vertices such that for every two vertices in, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.$

In computer science, a selection algorithm is an algorithm for finding the $th smallest value in a collection of ordered values, such as numbers. The value that it finds is called the th order statistic. Selection includes as special cases the problems of finding the minimum, median, and maximum element in the collection. Selection algorithms include quickselect, and the median of medians algorithm. When applied to a collection of values, these algorithms take linear time, as expressed using big O notation. For data that is already structured, faster algorithms may be possible; as an extreme case, selection in an already-sorted array takes time .$

In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. This allows the classification of NP-hard problems on a finer scale than in the classical setting, where the complexity of a problem is only measured as a function of the number of bits in the input. This appears to have been first demonstrated in Gurevich, Stockmeyer & Vishkin (1984). The first systematic work on parameterized complexity was done by Downey & Fellows (1999).

A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights.

In graph theory, a circle graph is the intersection graph of a chord diagram. That is, it is an undirected graph whose vertices can be associated with a finite system of chords of a circle such that two vertices are adjacent if and only if the corresponding chords cross each other.

<i>k</i>-d tree Multidimensional search tree for points in k dimensional space

In computer science, a k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key and creating point clouds. k-d trees are a special case of binary space partitioning trees.

<span class="mw-page-title-main">Maximal independent set</span> Independent set which is not a subset of any other independent set

In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set. In other words, there is no vertex outside the independent set that may join it because it is maximal with respect to the independent set property.

In computational geometry, Klee's measure problem is the problem of determining how efficiently the measure of a union of (multidimensional) rectangular ranges can be computed. Here, a d-dimensional rectangular range is defined to be a Cartesian product of d intervals of real numbers, which is a subset of R^d.

In graph theory and theoretical computer science, a maximum common induced subgraph of two graphs G and H is a graph that is an induced subgraph of both G and H, and that has as many vertices as possible.

In computer science, the maximum sum subarray problem, also known as the maximum segment sum problem, is the task of finding a contiguous subarray with the largest sum, within a given one-dimensional array A[1...n] of numbers. It can be solved in $time and space.$

Proximity problems is a class of problems in computational geometry which involve estimation of distances between geometric objects.

In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by Impagliazzo & Paturi (1999). It states that satisfiability of 3-CNF Boolean formulas cannot be solved in subexponential time, i.e., $for all constant, where n is the number of variables in the formula. The exponential time hypothesis, if true, would imply that P \neq NP, but it is a stronger statement. It implies that many computational problems are equivalent in complexity, in the sense that if one of them has a subexponential time algorithm then they all do, and that many known algorithms for these problems have optimal or near-optimal time complexity.$

In computational geometry, a maximum disjoint set (MDS) is a largest set of non-overlapping geometric shapes selected from a given set of candidate shapes.

In geometry, a covering of a polygon is a set of primitive units whose union equals the polygon. A polygon covering problem is a problem of finding a covering with a smallest number of units for a given polygon. This is an important class of problems in computational geometry. There are many different polygon covering problems, depending on the type of polygon being covered. An example polygon covering problem is: given a rectilinear polygon, find a smallest set of squares whose union equals the polygon.

In geometry, a partition of a polygon is a set of primitive units, which do not overlap and whose union equals the polygon. A polygon partition problem is a problem of finding a partition which is minimal in some sense, for example a partition with a smallest number of units or with units of smallest total side-length.

The geometric set cover problem is the special case of the set cover problem in geometric settings. The input is a range space $where is a universe of points in and is a family of subsets of called ranges, defined by the intersection of and geometric shapes such as disks and axis-parallel rectangles. The goal is to select a minimum-size subset of ranges such that every point in the universe is covered by some range in .$

<span class="mw-page-title-main">Guillotine partition</span> Process of partitioning a rectilinear polygon

Guillotine partition is the process of partitioning a rectilinear polygon, possibly containing some holes, into rectangles, using only guillotine-cuts. A guillotine-cut is a straight bisecting line going from one edge of an existing polygon to the opposite edge, similarly to a paper guillotine.

References

1 2 A. Naamad, D. T. Lee and W.-L. Hsu (1984). "On the Maximum Empty Rectangle Problem". Discrete Applied Mathematics. 8 (3): 267–277. doi: 10.1016/0166-218X(84)90124-0 .
↑ "Search Google Scholar for "largest empty rectangle" term usage".
↑ "Search Google Scholar for "maximal empty rectangle" term usage".
↑ "Search Google Scholar for "maximum empty rectangle" term usage".
↑ Jeffrey Ullman (1984). "Ch.9: Algorithms for VLSI Design Tools". Computational Aspects of VLSI . Computer Science Press. ISBN 0-914894-95-1. describes algorithms for polygon operations involved in electronic design automation (design rule checking, circuit extraction, placement and routing).
↑ Baird, H. S., Jones, S. E., Fortune, S.J. (1990). "Image segmentation by shape-directed covers". [1990] Proceedings. 10th International Conference on Pattern Recognition. Vol. 1. pp. 820–825. doi:10.1109/ICPR.1990.118223. ISBN 0-8186-2062-5. S2CID 62735730.{{cite book}}: CS1 maint: multiple names: authors list (link)
↑ Alok Aggearwal, Subhash Suri (1987). "Fast algorithms for computing the largest empty rectangle". Proceedings of the third annual symposium on Computational geometry - SCG '87. pp. 278–290. doi:10.1145/41958.41988. ISBN 0897912314. S2CID 18500442.
↑ B. Chazelle, R. L. Drysdale III and D. T. Lee (1984). "Computing the largest empty rectangle". STACS-1984, Lecture Notes in Computer Science. Lecture Notes in Computer Science. 166: 43–54. doi:10.1007/3-540-12920-0_4. ISBN 978-3-540-12920-2.
1 2 Thiagarajan, P. S. (23 November 1994). "Location of Largest Empty Rectangle among Arbitrary Obstacles". Foundations of Software Technology and Theoretical Computer Science. Springer. p. 159. ISBN 9783540587156.
↑ Subhas C Nandy; Bhargab B Bhattacharya; Sibabrata Ray (1990). "Efficient algorithms for identifying all maximal isothetic empty rectangles in VLSI layout design". Proc. FST & TCS – 10, Lecture Notes in Computer Science. Lecture Notes in Computer Science. 437: 255–269. doi:10.1007/3-540-53487-3_50. ISBN 978-3-540-53487-7.
↑ S.C. Nandy; B.B. Bhattacharya (1998). "Maximal Empty Cuboids among Points and Blocks". Computers & Mathematics with Applications. 36 (3): 11–20. doi: 10.1016/S0898-1221(98)00125-4 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[hsu1981-1] 1 2 A. Naamad, D. T. Lee and W.-L. Hsu (1984). "On the Maximum Empty Rectangle Problem". Discrete Applied Mathematics. 8 (3): 267–277. doi: 10.1016/0166-218X(84)90124-0 .

[2] "Search Google Scholar for "largest empty rectangle" term usage".

[3] "Search Google Scholar for "maximal empty rectangle" term usage".

[4] "Search Google Scholar for "maximum empty rectangle" term usage".

[5] Jeffrey Ullman (1984). "Ch.9: Algorithms for VLSI Design Tools". Computational Aspects of VLSI . Computer Science Press. ISBN 0-914894-95-1. describes algorithms for polygon operations involved in electronic design automation (design rule checking, circuit extraction, placement and routing).

[6] Baird, H. S., Jones, S. E., Fortune, S.J. (1990). "Image segmentation by shape-directed covers". [1990] Proceedings. 10th International Conference on Pattern Recognition. Vol. 1. pp. 820–825. doi:10.1109/ICPR.1990.118223. ISBN 0-8186-2062-5. S2CID 62735730.{{cite book}}: CS1 maint: multiple names: authors list (link)

[7] Alok Aggearwal, Subhash Suri (1987). "Fast algorithms for computing the largest empty rectangle". Proceedings of the third annual symposium on Computational geometry - SCG '87. pp. 278–290. doi:10.1145/41958.41988. ISBN 0897912314. S2CID 18500442.

[8] B. Chazelle, R. L. Drysdale III and D. T. Lee (1984). "Computing the largest empty rectangle". STACS-1984, Lecture Notes in Computer Science. Lecture Notes in Computer Science. 166: 43–54. doi:10.1007/3-540-12920-0_4. ISBN 978-3-540-12920-2.

[noniso-9] 1 2 Thiagarajan, P. S. (23 November 1994). "Location of Largest Empty Rectangle among Arbitrary Obstacles". Foundations of Software Technology and Theoretical Computer Science. Springer. p. 159. ISBN 9783540587156.

[10] Subhas C Nandy; Bhargab B Bhattacharya; Sibabrata Ray (1990). "Efficient algorithms for identifying all maximal isothetic empty rectangles in VLSI layout design". Proc. FST & TCS – 10, Lecture Notes in Computer Science. Lecture Notes in Computer Science. 437: 255–269. doi:10.1007/3-540-53487-3_50. ISBN 978-3-540-53487-7.

[11] S.C. Nandy; B.B. Bhattacharya (1998). "Maximal Empty Cuboids among Points and Blocks". Computers & Mathematics with Applications. 36 (3): 11–20. doi: 10.1016/S0898-1221(98)00125-4 .

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[1]

[9]

[10]

[11]