Geometric systems of unbiased representatives. (English) Zbl 1483.68461

Banik, Aritra; Bhattacharya, Bhaswar B.; Bhore, Sujoy; Martínez-Sandoval, Leonardo

Inf. Process. Lett. 176, Article ID 106232, 7 p. (2022).

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.

MSC:

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

Keywords:

computational geometry; systems of unbiased representatives; bicolorings; NP-hard problems; geometric ranges

Citations:

Zbl 1384.05118

References:

[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