@inproceedings{aa8507600117436d912f736d95dfe830,

title = "Computing the largest empty rectangle",

abstract = "We consider the following problem: Given a rectangle containing N 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(Nlog2N) expected time. This paper presents an O(N log3N) time, O(N log N) space algorithm to solve this problem. It uses a divide-and-conquer approach similar to the ones used by Strong and Bentley[1] and introduces a new notion of Voronoi diagram along with a method for efficient computation of certain functions over paths of a tree.",

author = "B. Chazelle and Drysdale, {R. L.} and Lee, {D. T.}",

note = "Funding Information: Let PI' P2' {"}''' Pn be the n points sorted by x-coordinate and Xmin, Xmax, Ymin' and Ymax be the boundaries of the bounding rectangle. Let the coordinates of point Pi be (xi, yi ). Our algorithm splits the points into two halves by x-coordinate and *Supported in part by the National Science Foundation under Grants MCS #and ECS 81-21741. A full version of this paper can be found in [4].; 1st Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985 ; Conference date: 11-04-1984 Through 13-04-1984",

year = "1984",

doi = "10.1007/3-540-12920-0_4",

language = "English (US)",

isbn = "9783540129202",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "43--54",

editor = "K. Mehlhorn and M. Fontet",

booktitle = "STACS 1984 - Symposium of Theoretical Aspects of Computer Science",

address = "Germany",

}