Computing the Largest Empty Rectangle
- 1 February 1986
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 15 (1) , 300-315
- https://doi.org/10.1137/0215022
Abstract
We consider the following problem: Given a rectangle containingN points, find the largest area subrectangle with sides parallel to those of the original rectangle which contains none of the given points. If the rectangle is a piece of fabric or sheet metal and the points are flaws, this problem is finding the largest-area rectangular piece which can be salvaged. A previously known result [13] takes O(N2) worst-case and O(N log N) expected time. This paper presents an O(N log N) time, O(N log N) space algorithm to solve this problem. It uses a divide-and-conquer approach similar to the ones used by Bentley [1] and introduces a new notion of Voronoi diagram along with a method for efficient computation of certain functions over paths of a treeKeywords
This publication has 9 references indexed in Scilit:
- On the maximum empty rectangle problemDiscrete Applied Mathematics, 1984
- Dynamic Voronoi diagramsIEEE Transactions on Information Theory, 1983
- Optimal Search in Planar SubdivisionsSIAM Journal on Computing, 1983
- Generalization of Voronoi Diagrams in the PlaneSIAM Journal on Computing, 1981
- Two-Dimensional Voronoi Diagrams in theLp-MetricJournal of the ACM, 1980
- An Optimal Worst Case Algorithm for Reporting Intersections of RectanglesIEEE Transactions on Computers, 1980
- Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage ApplicationsSIAM Journal on Computing, 1980
- An O ( n log n ) Algorithm for Rectilinear Minimal Spanning TreesJournal of the ACM, 1979
- Closest-point problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1975