查看文章

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 boundaries contain at least one member of P and the interior of the rectangle is empty. We propose a very simple algorithm based on standard data structure to locate a MER of largest area in the plane. The worst-case time complexity of our algorithm is O(n³). Though the worst-case space complexity is O(n²), it reserves O(nlogn) space on an average to maintain the required data structure during the execution of the algorithm.