Planar maximum-box problem revisited

Let B be a set of b blue points and R be a set of r red points in the plane. In this paper we study the problem of finding rectangles that contain the maximum number of blue points without containing any red points, known as the maximum-box problem. First we study this problem for axis-aligned rectangles, and propose an exact worst-case optimal O(r2+rb+blog⁡b) time algorithm using O(r+b) space to find all maximum boxes. We also provide a 2-approximation algorithm running in O((r+b)log⁡(r+b)) time and using O(r+b) space to find a single maximum box in the axis-aligned case. Then we generalize the exact algorithm for the axis-aligned case to find all arbitrarily oriented maximum boxes leading to a worst-case optimal O((r+b)2(r+log⁡b)) time algorithm using O((r+b)2) space to solve the problem. We conclude the paper by discussing time and space trade-offs. Our results improve the previously best known solutions to the maximum-box problem.