Largest empty rectangle: Difference between revisions

Content deleted Content added

Inline

Revision as of 10:16, 7 October 2014

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

A maximal empty rectangle (MER) is a rectangle which is not contained in another empty rectangle. Each side of a MER 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. ^[5] 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.^[6]

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

Domain: rectangle containing points

A problem first discused by Naamad, Lee and Hsu in 1983^[8] 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]

References

^ Template:Google scholar cite
^ Template:Google scholar cite
^ Template:Google scholar cite
^ 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". Proc. 10th International Conference on Pattern Recognition. 1: 820–825. doi:10.1109/ICPR.1990.118223.{{cite journal}}: CS1 maint: multiple names: authors list (link)
^ Alok Aggearwal, Subhash Suri (1987). "Fast algorithms for computing the largest empty rectangle". Proc. 3rd Annu. Symposium on Computational Geometry: 278–290. doi:10.1145/41958.41988.
^ B. Chazelle, R. L. Drysdale III and D. T. Lee (1984). "Computing the largest empty rectangle". STACS-1984, Lecture Notes in Computer Science. 166: 43–54. doi:10.1007/3-540-12920-0_4.
^ A. Naamad, D. T. Lee and W.-L. Hsu (1984). "On the Maximum Empty Rectangle Problem". Discrete Applied Mathematics: 267–277. doi:10.1016/0166-218X(84)90124-0.
^ ^a ^b "Location of Largest Empty Rectangle among Arbitrary Obstacles". Foundations of Software Technology and Theoretical Computer Science. p. 159.
^ 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. 437: 255–269. doi:10.1007/3-540-53487-3_50.{{cite journal}}: CS1 maint: multiple names: authors list (link)
^ S.C. Nandy and 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.

[1] Template:Google scholar cite

[2] Template:Google scholar cite

[3] Template:Google scholar cite

[4] 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).

[5] Baird, H. S., Jones, S. E., Fortune, S.J. (1990). "Image segmentation by shape-directed covers". Proc. 10th International Conference on Pattern Recognition. 1: 820–825. doi:10.1109/ICPR.1990.118223.{{cite journal}}: CS1 maint: multiple names: authors list (link)

[6] Alok Aggearwal, Subhash Suri (1987). "Fast algorithms for computing the largest empty rectangle". Proc. 3rd Annu. Symposium on Computational Geometry: 278–290. doi:10.1145/41958.41988.

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

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

[noniso-9] "Location of Largest Empty Rectangle among Arbitrary Obstacles". Foundations of Software Technology and Theoretical Computer Science. p. 159.

[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. 437: 255–269. doi:10.1007/3-540-53487-3_50.{{cite journal}}: CS1 maint: multiple names: authors list (link)

[11] S.C. Nandy and 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

@@ Line 1: / Line 1: @@
-In [[computational geometry]], the '''largest empty rectangle problem,'''<ref>[http://scholar.google.com/scholar?hl=en&lr=&q=%22largest+empty+rectangle%22&btnG=Search "largest empty rectangle" term usage]</ref> '''maximal empty rectangle problem'''<ref>[http://scholar.google.com/scholar?hl=en&lr=&q=%22maximal+empty+rectangle%22&btnG=Search "maximal empty rectangle" term usage]</ref> or '''maximum empty rectangle problem''',<ref>[http://scholar.google.com/scholar?hl=en&lr=&q=%22maximum+empty+rectangle%22&btnG=Search"maximum empty rectangle" term usage]</ref> 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 [[computational geometry]], the '''largest empty rectangle problem,'''<ref>{{google scholar cite|largest+empty+rectangle|Search Google Scholar for "largest empty rectangle" term usage}}</ref> '''maximal empty rectangle problem'''<ref>{{google scholar cite|maximal+empty+rectangle|Search Google Scholar for "maximal empty rectangle" term usage}}</ref> or '''maximum empty rectangle problem''',<ref>{{google scholar cite|maximum+empty+rectangle|Search Google Scholar for "maximum empty rectangle" term usage}}</ref> 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 circuit]]s. <ref>[[Jeffrey Ullman]], ''Computational Aspects of [[VLSI]]'', Computer Science Press, 1984, ISBN 0-914894-95-1—Chapter 9: "Algorithms for VLSI Design Tools" describes algorithms for [[polygon operations]] involved in electronic design automation ([[design rule checking]], [[circuit extraction]], [[placement and routing]]).</ref>
+The problems of this kind arise e.g., in [[electronic design automation]], in design and verification of [[physical layout]] of [[integrated circuit]]s. <ref>{{cite book|author=[[Jeffrey Ullman]]|title=Computational Aspects of [[VLSI]]|publisher=Computer Science Press|year=1984|isbn=0-914894-95-1|chapter=Ch.9: Algorithms for VLSI Design Tools}} describes algorithms for [[polygon operations]] involved in electronic design automation ([[design rule checking]], [[circuit extraction]], [[placement and routing]]).</ref>
-A '''maximal empty rectangle''' ('''MER''') is a rectangle which is not contained in another empty rectangle. Each side of a MER 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]]. <ref>Baird, H. S., Jones, S. E., Fortune, S.J. " Image segmentation by shape-directed covers",  Proc. 10th [[International Conference on  Pattern Recognition]], 1990, vol. 1, pp. 820–825, {{doi|10.1109/ICPR.1990.118223}}</ref> 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.
+A '''maximal empty rectangle''' ('''MER''') is a rectangle which is not contained in another empty rectangle. Each side of a MER 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]]. <ref>{{cite journal|author=Baird, H. S., Jones, S. E., Fortune, S.J.|title=Image segmentation by shape-directed covers|journal=Proc. 10th International Conference on  [[Pattern Recognition]]|year=1990|volume=1|pages=820–825|doi=10.1109/ICPR.1990.118223}}</ref> 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.'''<ref>[[Alok Aggearwal]], [[Subhash Suri]], "Fast algorithms for computing the largest empty rectangle", Proc. 3rd Annu. [[Symposium on Computational Geometry]], 1987, 278–290, {{doi|10.1145/41958.41988}} </ref>
+In terms of size measure, the two most common cases are the '''largest-area empty rectangle''' and '''largest-perimeter empty rectangle.'''<ref>{{cite journal|author=[[Alok Aggearwal]], [[Subhash Suri]]|title=Fast algorithms for computing the largest empty rectangle|journal=Proc. 3rd Annu. [[Symposium on Computational Geometry]]|year=1987|pages=278–290|doi=10.1145/41958.41988}}</ref>
 Another major classification is whether the rectangle is sought among [[axis-oriented]] or arbitrarily oriented rectangles.
@@ Line 14: / Line 14: @@
 ===Maximum-area square===
-The case when the sought rectangle is an axis-oriented square may be treated using [[Voronoi diagram]]s in <math>L_1</math>metrics for the corresponding obstacle set, similarly to the [[largest empty circle]] problem. In particular, for the [[#Domain: rectangle containing points|case of points within rectangle]] an optimal algorithm of [[time complexity]] <math>\Theta(n \log n)</math> is known. <ref>[[Bernard Chazelle|B. Chazelle]], R. L. Drysdale III and [[D. T. Lee]],  "Computing the largest empty rectangle", [[STACS]]-1984, ''[[Lecture Notes in Computer Science]]'', vol. 166, 1984, pp. 43–54, {{doi|10.1007/3-540-12920-0_4}}</ref>
+The case when the sought rectangle is an axis-oriented square may be treated using [[Voronoi diagram]]s in <math>L_1</math>metrics for the corresponding obstacle set, similarly to the [[largest empty circle]] problem. In particular, for the [[#Domain: rectangle containing points|case of points within rectangle]] an optimal algorithm of [[time complexity]] <math>\Theta(n \log n)</math> is known. <ref>{{cite journal|author=[[Bernard Chazelle|B. Chazelle]], R. L. Drysdale III and [[D. T. Lee]]|title=Computing the largest empty rectangle|journal=[[STACS]]-1984, [[Lecture Notes in Computer Science]]|volume= 166|year=1984|pages= 43–54|doi=10.1007/3-540-12920-0_4}}</ref>
 ===Domain: rectangle containing points===
-A problem first discused by Naamad, Lee and Hsu in 1983<ref>A. Naamad, [[D. T. Lee]] and W.-L. Hsu "On the Maximum Empty Rectangle Problem", ''[[Discrete Applied Mathematics]]'' 1984, pp. 267–277</ref> 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]] <math>O(\min(n^2,s \log n))</math>, where ''s'' is the number of feasible solutions, i.e., maximal empty rectangles. They also proved that <math>s= O(n^2)</math> and gave an example in which ''s'' is quadratic in ''n''. Afterwards a number of papers presented better algorithms  for the problem.
+A problem first discused by Naamad, Lee and Hsu in 1983<ref>{{cite journal|author=A. Naamad, [[D. T. Lee]] and W.-L. Hsu|title=On the Maximum Empty Rectangle Problem|journal=Discrete Applied Mathematics|year=1984|pages=267–277|doi=10.1016/0166-218X(84)90124-0}}</ref> 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]] <math>O(\min(n^2,s \log n))</math>, where ''s'' is the number of feasible solutions, i.e., maximal empty rectangles. They also proved that <math>s= O(n^2)</math> 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 polygon|isothetic]] line segments was first considered<!--a ref to the claim that it was "first --><ref name=noniso>"Location of Largest Empty Rectangle among Arbitrary Obstacles" [http://books.google.com/books?id=JWOA9M9CcX8C&pg=PA159&dq=%22maximal+empty+rectangle%22 p. 159]</ref> in 1990.<ref>"Efficient algorithms for identifying all maximal isothetic empty rectangles in VLSI layout design", Proc. FST & TCS – 10, ''[[Lecture Notes in Computer Science]], vol. 437, 1990, pp. 255–269</ref> Later a more general problem of empty isothetic rectangles among non-isothetic obstacles was considered.<ref name=noniso/>
+The problem of empty isothetic rectangles among [[Isothetic polygon|isothetic]] line segments was first considered<!--a ref to the claim that it was "first --><ref name=noniso>{{cite book|title=Foundations of Software Technology and Theoretical Computer Science|chapter=Location of Largest Empty Rectangle among Arbitrary Obstacles|url=http://books.google.com/books?id=JWOA9M9CcX8C&pg=PA159&dq=%22maximal+empty+rectangle%22|pages=159}}</ref> in 1990.<ref>{{cite journal|author= Subhas C Nandy,Bhargab B Bhattacharya,Sibabrata Ray|title=Efficient algorithms for identifying all maximal isothetic empty rectangles in VLSI layout design|journal=Proc. FST & TCS – 10, Lecture Notes in Computer Science|volume=437|year=1990|pages=255–269|doi=10.1007/3-540-53487-3_50}}</ref> Later a more general problem of empty isothetic rectangles among non-isothetic obstacles was considered.<ref name=noniso/>
 ==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. <ref>S.C. Nandy and B.B. Bhattacharya, "Maximal Empty Cuboids among Points and Blocks", ''Computers & Mathematics with Applications'', vol. 36, issue 3, 1998,  pp. 11–20, {{doi|10.1016/S0898-1221(98)00125-4 }}</ref>
+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. <ref>{{cite journal|author=S.C. Nandy and B.B. Bhattacharya|title=Maximal Empty Cuboids among Points and Blocks|journal=Computers & Mathematics with Applications|volume=36|issue=3|year=1998|pages= 11–20|doi=10.1016/S0898-1221(98)00125-4 }}</ref>
 ==See also==