Finding axis-parallel rectangles of fixed perimeter or area containing the largest number of points
Haim Y. Kaplan, Sasanka Roy, Micha Sharir · Computational Geometry · 2019
Let P be a set of n points in the plane in general position, and consider the problem of finding an axis-parallel rectangle with a given perimeter, or area, or diagonal, that encloses the maximum number of points of P . We present an exact algorithm that finds such a rectangle in O ( n 5 / 2 log n ) time, and, for the case of a fixed perimeter or diagonal, we also obtain (i) an improved exact algorithm that runs in O ( n k 3 / 2 log k ) time, and (ii) an approximation algorithm that finds, in O ( n + n k ε 5 log 5 / 2 n k log ( 1 ε log n k ) ) time, a rectangle of the given perimeter that contains at least ( 1 − ε ) k points of P , where k is the optimum value. We then show how to turn this algorithm into one that finds, for a given k , an axis-parallel rectangle of smallest perimeter (or area, or diagonal) that contains k points of P . We obtain the first subcubic algorithms for these problems, significantly improving the current state of the art.