Resumen de Bichromatic Discrepancy via Convex Partitions

S. Bereg, J.M. Díaz Báñez, D. Lara, P. Pérez Lantero, C. Seara, Jaime Urrutia Fucugauchi

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