Given a set R of r red points and a set B of b blue points in 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 along bounded degree algebraic trajectories. We design a compact and local quadratic-space kinetic data structure (KDS) for maintaining the optimal solution in O(rlog r+rlog b+b) time per each event. We also give an algorithm for solving the more general static problem where the maximum box can be arbitrarily oriented. This is an open problem in Aronov and Har-Peled (SIAM J. Comput. 38:899–921, 2008). We show that our approach can be used to solve this problem in O((r+b)2(rlog r+rlog b+b)) time. Finally we propose an efficient data structure to maintain an approximated solution of the kinetic Maximum Box Problem.
展开▼
机译：给定平面中r个r点的集合R和b个b点的集合B的集合，最大盒子问题的静态版本是找到一个等规盒子H，使得H∩R=∅且H∩B的基数为最大化。在本文中，我们考虑问题的动力学形式，其中R∪B中的点沿有界度代数轨迹运动。我们设计了一个紧凑的局部二次空间动力学数据结构（KDS），用于在每个事件的O（rlog r + rlog b + b）时间内保持最佳解决方案。我们还给出了一种算法，用于解决更一般的静态问题，其中最大框可以任意定向。这在Aronov和Har-Peled中是一个未解决的问题（SIAM J. Comput。38：899-921，2008）。我们证明了我们的方法可用于解决O（（r + b） 2 （rlog r + rlog b + b））时间的问题。最后，我们提出了一种有效的数据结构来维持动力学最大盒问题的近似解。
展开▼
