Computing the largest empty rectangle

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

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

7 Scopus citations


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
Number of pages12
ISBN (Print)9783540129202
StatePublished - 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


Other1st Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


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

Cite this