@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 = "Publisher Copyright: {\textcopyright} 1984, Springer Verlag. All rights reserved.; 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",

}