A. Aggarwal
S. Suri
ABSTRACT
We provide two algorithms for solving the following problem: Given a rectangle containing n points, compute the largest-area and the largest-perimeter subrectangles with sides parallel to the given rectangle that lie within this rectangle and that do not contain any points in their interior. For finding the largest-area empty rectangle, the first algorithm takes Ο(n log3 n) time and Ο(n) memory space and it simplifies the algorithm given by Chazelle, Drysdale and Lee which takes Ο(n log3 n) time but Ο(n log n) storage. The second algorithm for computing the largest-area empty rectangle is more complicated but it only takes Ο(n log2 n) time and Ο(n) memory space. The two algorithms for computing the largest-area rectangle can be modified to compute the largest-perimeter rectangle in Ο(n log2 n) and Ο(n log n) time, respectively. Since Ω(n log n) is a lower bound on time for computing the largest-perimeter empty rectangle, the second algorithm for computing such a rectangle is optimal within a multiplicative constant.
- 1.A. Aggarwal, M. M. Klawe, S. Moran, P. W. Shor, and R. WiIber, "Geometric Applications of a Matrix Searching Algorithm," Proc. of the Second Anmral Symposium on Computational Geometry, Yorktown Heights. New York, June 1986. Google Scholar
Digital Library
- 2.M. J. AtaRab and G. N. Fredrickson, "A Note on Finding the Maximum Empty Rectaogle," Discrete Applied Math., Vol. 13, pp. 87-91, 1986. Google ScholarDigital Library
- 3.M. J. Atallah and S. R Kosaraju, Manuscript, inprqwation ,Google Scholar
- 4.B. M ChazelIe. R L DrysdaIe BJ. and D. T. Lee, "Computing the Largest Empty Rectangle," SIAM J. of Computing. Vol. 15, No. 1, Feb. 1986, pp. 300-315. Also available as 'Technical Report No. CS 83-20, Department of Computer Science, Brown University, Nov. 1983. Google ScholarDigital Library
- 5.M. Mckenna, J. O'Rourke. and S. Suri, "Finding the Largest Rectangle in an Orthogonal Polygon," Proc. of the Urd Annual Allenon Conference on Communication, Control and Computing, Urbana-Champaingn, Illinois. October 1985.Google Scholar
- 6.A. Namaad, W. L Hsu, and D. T. Lee, "On Maximum Empty Rectangle Problem," Dite Applied Math., VoL 8, pp. 267-277.1984.Google Scholar
- 7.M. Tompa, Personal Communication, 1986.Google Scholar
Index Terms
- Fast algorithms for computing the largest empty rectangle
Recommendations
Largest empty rectangle among a point set
This work generalizes the classical problem of finding the largest empty rectangle among obstacles in 2D. Given a set P of n points, here a maximal empty rectangle (MER) is defined as a rectangle of arbitrary orientation such that each of its four ...
Faster Algorithms for Largest Empty Rectangles and Boxes
AbstractWe revisit a classical problem in computational geometry: finding the largest-volume axis-aligned empty box (inside a given bounding box) amidst n given points in d dimensions. Previously, the best algorithms known have running time for
Comments