Computing the largest empty rectangle

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 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(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.

Original languageEnglish (US)
Title of host publicationSTACS 1984 - Symposium of Theoretical Aspects of Computer Science
EditorsK. Mehlhorn, M. Fontet
PublisherSpringer Verlag
Pages43-54
Number of pages12
ISBN (Print)9783540129202
StatePublished - Jan 1 1984
Externally publishedYes
Event1st Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985 - Paris, France
Duration: Apr 11 1984Apr 13 1984

Publication series

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

Other

Other1st Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985
CountryFrance
CityParis
Period4/11/844/13/84

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Computing the largest empty rectangle'. Together they form a unique fingerprint.

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