Bichromatic Discrepancy via Convex Partitions

• S. Bereg ^[5] ; J.M. Díaz Báñez ^[1] ; D. Lara ^[2] ; P. Pérez Lantero ^[3] ; C. Seara ^[4] ; J. Urrutia ^[2]
  1. [1] Universidad de Sevilla

     Universidad de Sevilla

     Sevilla, España

     
  2. [2] Universidad Nacional Autónoma de México

     Universidad Nacional Autónoma de México

     México

     
  3. [3] Universidad de La Habana

     Universidad de La Habana

     Cuba

     
  4. [4] Universitat Politècnica de Catalunya

     Universitat Politècnica de Catalunya

     Barcelona, España

     
  5. [5] 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. 259-265
• Idioma: inglés
• Texto completo no disponible (Saber más ...)
• Resumen

  • Let R be a set of red points and B a set of blue points on the plane. In this paper we introduce a new concept for measuring how mixed the elements of S = R [ B are. The discrepancy of a set X ½ S is ||X \ R| − |X \ B||. We say that a partition ¦ = {S1, S2, . . . , Sk} of S is convex if the convex hulls of its members are pairwise disjoint. The discrepancy of a convex partition of S is the minimum discrepancy of the sets Si. The discrepancy of S is the discrepancy of the convex partition of S with maximum discrepancy. We study the problem of computing the discrepancy of a bichromatic point set. We divide the study in general convex partitions for both general set of points and points in convex position, and also when the partition is given by a line. In this case we prove that this problem is 3SUM-hard.