The Maximum Box Problem for Moving Points on the Plane

• S. Bereg ^[3] ; J.M. Díaz Báñez ^[1] ; P. Pérez Lantero ^[2] ; I. Ventura ^[1]
  1. [1] Universidad de Sevilla

     Universidad de Sevilla

     Sevilla, España

     
  2. [2] Universidad de La Habana

     Universidad de La Habana

     Cuba

     
  3. [3] University of Texas

  Mostrar afiliaciones +
• Localización: XIII Encuentros de Geometría Computacional: Zaragoza, del 29 de junio al 1 de julio de 2009 / Alfredo García Olaverri (ed. lit.) , Javier Tejel Altarriba (ed. lit.) , 2009, ISBN 978-84-92774-11-1, págs. 235-242
• Idioma: inglés
• Texto completo no disponible (Saber más ...)
• Resumen

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