Combinatorics

Mathematics

Multiplicative function

Perimeter

Algorithm

Data structure

Mathematical analysis

Programming language

Geometry

Constant (computer programming)

Computer science

Rectangle

Time complexity

Binary logarithm

Upper and lower bounds

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 not contain any points in their interior. For finding the largest-area empty rectangle, the first algorithm takes Ο(n log3 n) time and Ο(n) memory space and it simplifies the algorithm given by Chazelle, Drysdale and Lee which takes Ο(n log3 n) time but Ο(n log n) storage. The second algorithm for computing the largest-area empty rectangle is more complicated but it only takes Ο(n log2 n) time and Ο(n) memory space. The two algorithms for computing the largest-area rectangle can be modified to compute the largest-perimeter rectangle in Ο(n log2 n) and Ο(n log n) time, respectively. Since Ω(n log n) is a lower bound on time for computing the largest-perimeter empty rectangle, the second algorithm for computing such a rectangle is optimal within a multiplicative constant.

Fast algorithms for computing the largest empty rectangle