Computing the largest empty rectangle

B. Chazelle; R. L. Drysdale; D. T. Lee

doi:10.1007/3-540-12920-0_4

Computing the largest empty rectangle

B. Chazelle, R. L. Drysdale, D. T. Lee

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

8 Scopus citations

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(N²) worst-case and O(Nlog²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 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.

Original language	English (US)
Title of host publication	STACS 1984 - Symposium of Theoretical Aspects of Computer Science
Editors	K. Mehlhorn, M. Fontet
Publisher	Springer Verlag
Pages	43-54
Number of pages	12
ISBN (Print)	9783540129202
DOIs	https://doi.org/10.1007/3-540-12920-0_4
State	Published - 1984
Externally published	Yes
Event	1st Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985 - Paris, France Duration: Apr 11 1984 → Apr 13 1984

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	166 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	1st Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985
Country/Territory	France
City	Paris
Period	4/11/84 → 4/13/84

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-12920-0_4

Cite this

Chazelle, B., Drysdale, R. L., & Lee, D. T. (1984). Computing the largest empty rectangle. In K. Mehlhorn, & M. Fontet (Eds.), STACS 1984 - Symposium of Theoretical Aspects of Computer Science (pp. 43-54). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 166 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-12920-0_4

@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",

}

Chazelle, B, Drysdale, RL & Lee, DT 1984, Computing the largest empty rectangle. in K Mehlhorn & M Fontet (eds), STACS 1984 - Symposium of Theoretical Aspects of Computer Science. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 166 LNCS, Springer Verlag, pp. 43-54, 1st Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985, Paris, France, 4/11/84. https://doi.org/10.1007/3-540-12920-0_4

Computing the largest empty rectangle. / Chazelle, B.; Drysdale, R. L.; Lee, D. T.
STACS 1984 - Symposium of Theoretical Aspects of Computer Science. ed. / K. Mehlhorn; M. Fontet. Springer Verlag, 1984. p. 43-54 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 166 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Computing the largest empty rectangle

AU - Chazelle, B.

AU - Drysdale, R. L.

AU - Lee, D. T.

PY - 1984

Y1 - 1984

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84977533164&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84977533164&partnerID=8YFLogxK

U2 - 10.1007/3-540-12920-0_4

DO - 10.1007/3-540-12920-0_4

M3 - Conference contribution

AN - SCOPUS:84977533164

SN - 9783540129202

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 43

EP - 54

BT - STACS 1984 - Symposium of Theoretical Aspects of Computer Science

A2 - Mehlhorn, K.

A2 - Fontet, M.

PB - Springer Verlag

T2 - 1st Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985

Y2 - 11 April 1984 through 13 April 1984

ER -

Chazelle B, Drysdale RL, Lee DT. Computing the largest empty rectangle. In Mehlhorn K, Fontet M, editors, STACS 1984 - Symposium of Theoretical Aspects of Computer Science. Springer Verlag. 1984. p. 43-54. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-12920-0_4

Computing the largest empty rectangle

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this