The Maximum Box Problem for Moving Points on the Plane
Sergey Bereg, J.M. Díaz Báñez, Pablo Pérez Lantero, Inmaculada Ventura · 2009
Given a set R of r red points and a set B of b blue points on the plane, the static version of the Maximum Box Problem is to find an isothetic box H such that H ∩ R = ∅ and the cardinality of H ∩B is maximized. In this paper, we consider a kinetic version of the problem where the points in R ∪ B move according to algebraic functions. We design a compact and local quadratic-space kinetic data structure (KDS) for maintaining the optimal solution in O(r log r + r log b) time per each event. We also study the general static problem where the maximum box can be arbitrarily oriented. This is an open problem in [1]. We show that our approach can be used to solve this problem in O((r + b)2(r log r + r log b)) time. Finally we propose an efficient data structure to maintain an approximated solution of the kinetic Maximum Box Problem. 1