Bichromatic Discrepancy via Convex Partitions
Sergey Bereg, J.M. Díaz Báñez, Dolores Lara, Pablo Pérez Lantero, Carlos Seara, Jaime Urrutia Fucugauchi · 2009
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.