Convex equipartitions of colored point sets. (English) Zbl 1407.52031
Summary: We show that any \(d\)-colored set of points in general position in \({\mathbb {R}}^d\) can be partitioned into \(n\) subsets with disjoint convex hulls such that the set of points and all color classes are partitioned as evenly as possible. This extends results by A. F. Holmsen et al. [Comput. Geom. 65, 35–42 (2017; Zbl 1377.65026)] and establishes a special case of their general conjecture. Our proof utilizes a result obtained independently by P. Soberón [Mathematika 58, No. 1, 71–76 (2012; Zbl 1267.28005)] and by R. N. Karasev in [“Equipartition of several measures”, Preprint, arXiv:1011.4762], on simultaneous equipartitions of \(d\) continuous measures in \({\mathbb {R}}^d\) by \(n\) convex regions. This gives a convex partition of \({\mathbb {R}}^d\) with the desired properties, except that points may lie on the boundaries of the regions. In order to resolve the ambiguous assignment of these points, we set up a network flow problem. The equipartition of the continuous measures gives a fractional flow. The existence of an integer flow then yields the desired partition of the point set.
MSC:
| 52C35 | Arrangements of points, flats, hyperplanes (aspects of discrete geometry) |
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
References:
| [1] | Aichholzer, O., Cabello, S., Fabila-Monroy, R., Flores-Peñaloza, D., Hackl, T., Huemer, C., Hurtado, F., Wood, D.R.: Edge-removal and non-crossing configurations in geometric graphs. Discrete Math. Theor. Comput. Sci. (DMTCS) 12(1), 75-86 (2010) · Zbl 1250.05060 |
| [2] | Akiyama, J., Alon, N.: Disjoint simplices and geometric hypergraphs. In: Bloom, G.A., Graham, R.L., Malkevitch, J. (eds.) Combinatorial Mathematics: Proceedings of the Third International Conference, New York 1985. Annals of the New York Academy of Sciences, vol. 555, pp. 1-3. New York Academy of Sciences, New York (1989) · Zbl 0734.05064 |
| [3] | Bespamyatnikh, S., Kirkpatrick, D., Snoeyink, J.: Generalizing ham sandwich cuts to equitable subdivisions. Discrete Comput. Geom. 24(4), 605-622 (2000) · Zbl 0966.68156 · doi:10.1007/s4540010065 |
| [4] | Blagojević, P.V.M., Ziegler, G.M.: Convex equipartitions via equivariant obstruction theory. Isr. J. Math. 200(1), 49-77 (2014) · Zbl 1305.52005 · doi:10.1007/s11856-014-1006-6 |
| [5] | Holmsen, A.F., Kynčl, J., Valculescu, C.: Near equipartitions of colored point sets. Comput. Geom. 65, 35-42 (2017) · Zbl 1377.65026 · doi:10.1016/j.comgeo.2017.05.001 |
| [6] | Ito, H., Uehara, H., Yokoyama, M.: \[22\]-Dimension ham sandwich theorem for partitioning into three convex pieces. In: Akiyama, J., Kano, M., Urabe, M. (eds.) Discrete and Computational Geometry (JCDCG’98). Lecture Notes in Computer Science, vol. 1763, pp. 129-157. Springer, Berlin (2000) · Zbl 0973.52005 |
| [7] | Kano, M., Kynčl, J.: The hamburger theorem. Comput. Geom. 68, 167-173 (2018) · Zbl 1380.05068 |
| [8] | Kano, M., Suzuki, K., Uno, M.: Properly colored geometric matchings and \[33\]-trees without crossings on multicolored points in the plane. In: Akiyama, J., Ito, H., Sakai, T. (eds.) Discrete and Computational Geometry and Graphs. Lecture Notes in Computer Science, vol. 8845, pp. 96-111. Springer, Cham (2014) · Zbl 1452.05064 |
| [9] | Karasev, R.N.: Equipartition of several measures. arXiv:1011.4762v7 (2010) |
| [10] | Karasev, R., Hubard, A., Aronov, B.: Convex equipartitions: the spicy chicken theorem. Geom. Dedicata 170, 263-279 (2014) · Zbl 1301.52010 · doi:10.1007/s10711-013-9879-5 |
| [11] | Sakai, T.: Balanced convex partitions of measures in \[{\mathbb{R}}^2\] R2. Graphs Comb. 18(1), 169-192 (2002) · Zbl 1002.52002 · doi:10.1007/s003730200011 |
| [12] | Schrijver, A.: Combinatorial Optimization—Polyhedra and Efficiency. Vol. A: Paths, Flows, Matchings. Algorithms and Combinatorics, vol. 24. Springer, Berlin (2003) · Zbl 1041.90001 |
| [13] | Soberón, P.: Balanced convex partitions of measures in \[{\mathbb{R}}^d\] Rd. Mathematika 58(1), 71-76 (2012) · Zbl 1267.28005 · doi:10.1112/S0025579311001914 |
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.
