[Back]

A. Banik, B. Bhattacharya, S. Bhore, L. Martinez-Sandoval:
"Geometric Systems of Unbiased Representatives";
Talk: Canadian Conference in Computational Geometry, Edmonton, Canada,; 2019-08-08 - 2019-08-10.

Let P be a set of points in Rd, B a bicoloring of P and O
a family of geometric objects (that is, intervals, boxes,
balls, etc). An object from O is called balanced with
respect to B if it contains the same number of points
from each color of B. For a collection B of bicolorings of
P, a geometric system of unbiased representatives (G-
SUR) is a subset O0 O such that for any bicoloring
B of B there is an object in O0 that is balanced with
respect to B.
We study the problem of nding G-SURs. We obtain
general bounds on the size of G-SURs consisting of in-
tervals, size-restricted intervals, axis-parallel boxes and
Euclidean balls. We show that the G-SUR problem is
NP-hard even in the simple case of points on a line and
interval ranges. Furthermore, we study a related prob-
lem on determining the size of the largest and smallest
balanced intervals for points on the real line with a ran-
dom distribution and coloring.
Our results are a natural extension to a geometric con-
text of the work initiated by Balachandran et al. on
arbitrary systems of unbiased representatives.