### 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 takes O(N**2) worst-case and O(N log**2 N) expected time. This paper presents an O(N log**3 N) time, O(N log N) space algorithm to solve this problem. It uses a divide-and-conquer approach 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) |
---|---|

Pages (from-to) | 300-315 |

Number of pages | 16 |

Journal | SIAM Journal on Computing |

Volume | 15 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1 1986 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Computer Science(all)
- Mathematics(all)

## Fingerprint Dive into the research topics of 'COMPUTING THE LARGEST EMPTY RECTANGLE.'. Together they form a unique fingerprint.

## Cite this

*SIAM Journal on Computing*,

*15*(1), 300-315. https://doi.org/10.1137/0215022