Computing the Largest Empty Rectangle

We provide two algorithms for solving the following problem: Given a rectangle containing n points, compute the largest-area and the largest-perimeter subrectangles with sides parallel to the given rectangle that lie within this rectangle and that do ...

This work generalizes the classical problem of finding the largest empty rectangle among obstacles in 2D. Given a set P of n points, here a maximal empty rectangle (MER) is defined as a rectangle of arbitrary orientation such that each of its four ...

This paper presents an algorithm for identifying a maximal empty-staircase-polygon (MESP) of largest area, among a set of n points on a rectangular floor. A staircase polygon is an isothetic polygon bounded by two monotonically rising (falling) ...