Geometric systems of unbiased representatives. (English) Zbl 1483.68461

Summary: Let \(P\) be a finite point set in \(\mathbb{R}^d\), \(B\) be a bicoloring of \(P\) and \(\mathcal{O}\) be a family of geometric objects (that is, intervals, boxes, balls, etc). An object from \(\mathcal{O}\) is called balanced with respect to \(B\) if it contains the same number of points from each color of \(B\). For a collection \(\mathcal{B}\) of bicolorings of \(P\), a geometric system of unbiased representatives (G-SUR) is a subset \(\mathcal{O}'\subseteq\mathcal{O}\) such that for any bicoloring \(B\) of \(\mathcal{B}\) there is an object in \(\mathcal{O}'\) that is balanced with respect to \(B\).
We pose and study problems on finding G-SURs. We obtain general bounds on the size of G-SURs consisting of intervals, 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 problem on determining the size of the largest and smallest balanced intervals for points on the real line with a random distribution and coloring.
Our results are a natural extension to a geometric context of the work initiated by N. Balachandran et al. [Discrete Math. 341, No. 6, 1732–1739 (2018; Zbl 1384.05118)] on arbitrary systems of unbiased representatives.


68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)


Zbl 1384.05118
Full Text: DOI arXiv


[1] Aichholzer, Oswin; Atienza, Nieves; Díaz-Báñez, José M.; Fabila-Monroy, Ruy; Flores-Peñaloza, David; Pérez-Lantero, Pablo; Vogtenhuber, Birgit; Urrutia, Jorge, Computing balanced islands in two colored point sets in the plane, Inf. Process. Lett., 135, 28-32 (2018) · Zbl 1476.68264
[2] Balachandran, Niranjan; Mathew, Rogers; Mishra, Tapas Kumar; Pal, Sudebkumar Prasant, Induced-bisecting families of bicolorings for hypergraphs, Discrete Math., 341, 6, 1732-1739 (2018) · Zbl 1384.05118
[3] Balachandran, Niranjan; Mathew, Rogers; Mishra, Tapas Kumar; Pal, Sudebkumar Prasant, Bisecting and d-secting families for set systems, Discrete Appl. Math., 280, 2-13 (2020) · Zbl 1439.05169
[4] Bereg, Sergey; Díaz-Báñez, José Miguel; Fabila-Monroy, R.; Pérez-Lantero, Pablo; Ramírez-Vigueras, A.; Sakai, Toshinori; Urrutia, Jorge; Ventura, Inmaculada, On balanced 4-holes in bichromatic point sets, Comput. Geom., 48, 3, 169-179 (2015) · Zbl 1307.52009
[5] Bereg, Sergey; Hurtado, Ferran; Kano, Mikio; Korman, Matias; Lara, Dolores; Seara, Carlos; Silveira, Rodrigo I.; Urrutia, Jorge; Verbeek, Kevin, Balanced partitions of 3-colored geometric sets in the plane, Discrete Appl. Math., 181, 21-32 (2015) · Zbl 1304.05008
[6] De Berg, Mark; Van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried, Computational geometry, (Computational Geometry (1997), Springer), 1-17 · Zbl 0877.68001
[7] Dickson, T. J., On a problem concerning separating systems of a finite set, J. Comb. Theory, 7, 3, 191-196 (1969) · Zbl 0208.02403
[8] Katona, Gyula, On separating systems of a finite set, J. Comb. Theory, 1, 2, 174-194 (1966) · Zbl 0144.00501
[9] Lo, Chi-Yuan; Matoušek, Jiří; Steiger, William, Algorithms for ham-sandwich cuts, Discrete Comput. Geom., 11, 4, 433-452 (1994) · Zbl 0806.68061
[10] Matousek, Jiri, Geometric Discrepancy: An Illustrated Guide, Vol. 18 (2009), Springer Science & Business Media · Zbl 0930.11060
[11] Rényi, A., On random generating elements of a finite boolean algebra, Acta Sci. Math. Szeged, 22, 75-81, 4 (1961) · Zbl 0099.12204
[12] Spencer, Joel, Minimal completely separating systems, J. Comb. Theory, 8, 4, 446-447 (1970) · Zbl 0185.03201
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.