×

Near equipartitions of colored point sets. (English) Zbl 1377.65026

The authors prove two theorems regarding partitions of coloured point sets. The first one deals with a set of \(nk\) 2-coloured points in general position in the plane (no three of the points are collinear), where \(n\) is minimal number of points of each colour. They prove that there exist \(n\) subsets with disjoint convex hulls (no two of them intersect) with the following properties (1) each pairwise disjoint convex subset contains \(k\) of the points, and (2) each pairwise disjoint convex subset contains points of both colours. The second theorem relates to partitions of coloured point sets in a space of higher dimensions. Specially, for a given set of \(n(d+1)\) \(d\)-coloured points in general position in a \(d\)-dimensional space there exist \(n\) pairwise disjoint convex subsets of \(d+1\) points, each of them containing points of all \(d\) colours.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
52C35 Arrangements of points, flats, hyperplanes (aspects of discrete geometry)
65D19 Computational issues in computer and robotic vision
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aichholzer, O.; Cabello, S.; Fabila-Monroy, R.; Flores-Pñaloza, D.; Hackl, T.; Huemer, C.; Hurtado, F.; Wood, D., Edge-removal and non-crossing configurations in geometric graphs, Discrete Math. Theor. Comput. Sci., 12, 1, 75-86 (2010) · Zbl 1250.05060
[2] Akiyama, J.; Alon, N., Disjoint simplices and geometric hypergraphs, (Combinatorial Mathematics: Proceedings of the Third International Conference. Combinatorial Mathematics: Proceedings of the Third International Conference, New York, 1989. Combinatorial Mathematics: Proceedings of the Third International Conference. Combinatorial Mathematics: Proceedings of the Third International Conference, New York, 1989, Ann. New York Acad. Sci., vol. 555 (1985), New York Acad. Sci.: New York Acad. Sci. New York), 1-3 · 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
[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
[5] Elton, J. H.; Hill, T. P., A stronger conclusion to classical ham sandwich theorem, Eur. J. Comb., 32, 5, 657-661 (2011) · Zbl 1228.52015
[6] Ito, H.; Uehara, H.; Yokoyama, M., 2-dimension ham sandwich theorem for partitioning into three convex pieces, (Akiyama, J.; Kano, M.; Urabe, M., Discrete and Computational Geometry: Japanese Conference, Revised Papers. Discrete and Computational Geometry: Japanese Conference, Revised Papers, JCDCG’98, Tokyo, Japan, December 9-12, 1998 (2000), Springer), 129-157 · Zbl 0973.52005
[7] Kaneko, A.; Kano, M., Discrete geometry on red and blue points in the plane - a survey, (Discrete and Computational Geometry. Discrete and Computational Geometry, Algorithms and Combinatorics, vol. 25 (2003), Springer), 551-570 · Zbl 1079.52505
[8] Kaneko, A.; Kano, M., Semi-balanced partitions of two sets of points and embeddings of rooted forests, Int. J. Comput. Geom. Appl., 15, 3, 229-238 (2005) · Zbl 1104.68122
[9] Kaneko, A.; Kano, M.; Suzuki, K., Path coverings of two sets of points in the plane, (Pach, J., Towards a Theory of Geometric Graphs. Towards a Theory of Geometric Graphs, Contemp. Math., vol. 342 (2004), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 99-111 · Zbl 1064.52013
[10] Kano, M.; Kynčl, J., The hamburger theorem (2016), in press
[11] Kano, M.; Suzuki, K.; Uno, M., Properly colored geometric matchings and 3-trees without crossings on multicolored points in the plane, (Discrete and Computational Geometry and Graphs. Discrete and Computational Geometry and Graphs, Lecture Notes in Comput. Sci., vol. 8845 (2014), Springer), 96-111 · Zbl 1452.05064
[12] Kano, M.; Uno, M., General balanced subdivision of two sets of points in the plane, (Discrete Geometry, Combinatorics and Graph Theory. Discrete Geometry, Combinatorics and Graph Theory, Lecture Notes in Comput. Sci., vol. 4381 (2007), Springer), 79-87 · Zbl 1149.52302
[13] Kano, M.; Uno, M., Balanced subdivisions with boundary condition of two sets of points in the plane, Int. J. Comput. Geom. Appl., 20, 5, 527-541 (2010) · Zbl 1213.65036
[14] Karasev, R.; Hubard, A.; Aronov, B., Convex equipartitions: the spicy chicken theorem, Geom. Dedic., 170, 263-279 (2014) · Zbl 1301.52010
[15] Matoušek, J., Lectures on Discrete Geometry, Graduate Texts in Mathematics, vol. 212 (2002), Springer: Springer New York · Zbl 0999.52006
[16] Matoušek, J., Using the Borsuk-Ulam Theorem, Universitext (2003), Springer · Zbl 1016.05001
[17] Sakai, T., Balanced convex partitions of measures in \(R^2\), Graphs Comb., 18, 1, 169-192 (2002) · Zbl 1002.52002
[18] Soberón, P., Balanced convex partitions of measures in \(R^d\), Mathematika, 58, 1, 71-76 (2012) · Zbl 1267.28005
[19] Stone, A. H.; Tukey, J. W., Generalized “sandwich” theorems, Duke Math. J., 9, 356-359 (1942) · Zbl 0061.38405
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.