Resumen de The Maximum Box Problem for Moving Points on the Plane

S. Bereg, J.M. Díaz Báñez, P. Pérez Lantero, Inmaculada Ventura Molina

• 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.