Fast algorithms for computing the largest empty rectangle

Abstract

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 O(n log3n) time and O(n) memory space and it simplifies the algorithm given by Chazeile, Drysdale and Lee which takes O(n log3 n) time but O(n log n) storage. The second algorithm for computing the largest-area empty rectangle is more complicated but it only takes O(n log2n) time and O(n) memory space. The two algorithms for computing the largest-area rectangle can be modified to compute the largest-perimeter rectangle in O(n log2 n) and O(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.