{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T01:15:12Z","timestamp":1773882912592,"version":"3.50.1"},"reference-count":108,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,7,16]],"date-time":"2020-07-16T00:00:00Z","timestamp":1594857600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,7,16]],"date-time":"2020-07-16T00:00:00Z","timestamp":1594857600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["19K03597"],"award-info":[{"award-number":["19K03597"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Universidad Nacional Autonoma de Mexico","award":["PAPIIT Grant IN102117"],"award-info":[{"award-number":["PAPIIT Grant IN102117"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2021,1]]},"DOI":"10.1007\/s00373-020-02210-8","type":"journal-article","created":{"date-parts":[[2020,7,16]],"date-time":"2020-07-16T19:03:45Z","timestamp":1594926225000},"page":"1-53","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Discrete Geometry on Colored Point Sets in the Plane\u2014A Survey"],"prefix":"10.1007","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7545-0327","authenticated-orcid":false,"given":"Mikio","family":"Kano","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jorge","family":"Urrutia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,7,16]]},"reference":[{"key":"2210_CR1","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/S0166-218X(99)00042-6","volume":"93","author":"M Abellanas","year":"1999","unstructured":"Abellanas, M., Garc\u00eda, J., Hern\u00e1ndez, G., Noy, M., Ramos, P.: Bipartite embeddings of trees in the plane. Discrete Appl. Math. 93, 141\u2013148 (1999)","journal-title":"Discrete Appl. Math."},{"key":"2210_CR2","unstructured":"Abellanas, M., Garc\u00eda, A., Hurtado, F., Tejel, J.: Caminos alternantes. Actas X Encuentros de Geometr\u00eda Computacional (in spanish) 7\u201312 (2003)"},{"issue":"6","key":"2210_CR3","first-page":"29","volume":"21","author":"M \u00c1brego","year":"2019","unstructured":"\u00c1brego, M., Fern\u00e1ndez-Merchant, S., Kano, M., Orden, D., P\u00e9rez-Lantero, P., Seara, C., Tejel, J.: $$K_{1,3}$$-covering red and blue points in the plane. Discrete Math. Theor. Comput. Sci. 21(6), 29 (2019)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"2210_CR4","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.ipl.2018.02.008","volume":"135","author":"O Aichholzer","year":"2018","unstructured":"Aichholzer, O., Atienza, N., D\u00edas-B\u00e1\u00f1ez, J.M., Fabila-Monroy, R., Flores-Pe\u00f1aloza, D., P\u00e9rez-Lantero, P., Vogtenhuber, B., Urrutia, J.: Computing balanced islands in two colored point sets in the plane. Inf. Process. Lett. 135, 28\u201332 (2018)","journal-title":"Inf. Process. Lett."},{"key":"2210_CR5","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.comgeo.2017.05.003","volume":"68","author":"O Aichholzer","year":"2018","unstructured":"Aichholzer, O., Barba, L., Hackl, T., Pilz, A., Vogtenhuber, B.: Linear transformation distance for bichromatic matchings. Comput. Geom. 68, 77\u201388 (2018)","journal-title":"Comput. Geom."},{"key":"2210_CR6","first-page":"75","volume":"12","author":"O Aichholzer","year":"2010","unstructured":"Aichholzer, O., Cabello, S., Fabila-Monroy, R., Flores-Pe\u00f1aloza, D., Hackl, T., Huemer, C., Hurtado, F., Wood, D.: Edge-removal and non-crossing configurations in geometric graphs. Discrete Math. Theor. Comput. Sci. 12, 75\u201386 (2010)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"2210_CR7","doi-asserted-by":"publisher","first-page":"934","DOI":"10.1016\/j.comgeo.2009.04.002","volume":"42","author":"O Aichholzer","year":"2009","unstructured":"Aichholzer, O., Fabila-Monroy, R., Flores-Pe\u00f1aloza, D., Hackl, T., Huemer, C., Urrutia, J.: Empty monochromatic triangles. Comput. Geom. 42, 934\u2013938 (2009)","journal-title":"Comput. Geom."},{"key":"2210_CR8","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1007\/s00454-013-9565-2","volume":"42","author":"O Aichholzer","year":"2014","unstructured":"Aichholzer, O., Fabila-Monroy, R., Hackl, T., Huemer, C., Urrutia, J.: Empty monochromatic simplices. Discrete Comput. Geom. 42, 362\u2013393 (2014)","journal-title":"Discrete Comput. Geom."},{"key":"2210_CR9","doi-asserted-by":"crossref","unstructured":"Aichholzer, O., Hackl, T., Huemer, C., Hurtado, F., Vogtenhuber, B.: Large bichromatic point sets admit empty monochromatic 4-gons. SIAM J. Discrete Math. 23, 2147\u20132155 (2009-10)","DOI":"10.1137\/090767947"},{"key":"2210_CR10","doi-asserted-by":"crossref","unstructured":"Akiyama, J., Alon, N.: Disjoint simplices and geometric hypergraphs, Combinatorial Combinatorial Mathematics: Proceedings of the third international conference (New York, 1985), Ann. New York Acad. Sci. vol. 555, pp. 1\u20133. New York Acad. Sci., New York (1989)","DOI":"10.1111\/j.1749-6632.1989.tb22429.x"},{"key":"2210_CR11","doi-asserted-by":"crossref","unstructured":"Akiyama, J., Kaneko, A., Kano, M., Nakamura, G., Rivera-Campo, E., Tokunaga, S., Urrutia, J.: Radical perfect partitions of convex sets in the plane Discrete and computational geometry (Tokyo, 1998), Lecture Notes in Comput. Sci., vol. 1763, pp. 1\u201313. Springer, Berlin (2000)","DOI":"10.1007\/978-3-540-46515-7_1"},{"key":"2210_CR12","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0012-365X(90)90276-N","volume":"84","author":"J Akiyama","year":"1990","unstructured":"Akiyama, J., Urrutia, J.: Simple bichromatic path problem. Discrete Math. 84, 101\u2013103 (1990)","journal-title":"Discrete Math."},{"key":"2210_CR13","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/s00454-012-9450-4","volume":"49","author":"A Akopyan","year":"2013","unstructured":"Akopyan, A., Karasev, R.: Cutting the same fraction of several measures. Discrete Comput. Geom. 49, 402\u2013410 (2013)","journal-title":"Discrete Comput. Geom."},{"key":"2210_CR14","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0001-8708(87)90055-7","volume":"63","author":"N Alon","year":"1987","unstructured":"Alon, N.: Splitting necklaces. Adv. Math. 63, 247\u2013253 (1987)","journal-title":"Adv. Math."},{"key":"2210_CR15","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1090\/S0002-9939-1986-0861764-9","volume":"98","author":"N Alon","year":"1986","unstructured":"Alon, N., West, D.B.: The Borsuk\u2013Ulam theorem and bisection of necklaces. Proc. Am. Math. Soc. 98, 623\u2013628 (1986)","journal-title":"Proc. Am. Math. Soc."},{"key":"2210_CR16","doi-asserted-by":"publisher","first-page":"622","DOI":"10.1016\/j.comgeo.2014.08.009","volume":"48","author":"G Aloupis","year":"2015","unstructured":"Aloupis, G., Barba, L., Langerman, S., Souvaine, D.L.: Bichromatic compatible matchings. Comput. Geom. 48, 622\u2013633 (2015)","journal-title":"Comput. Geom."},{"key":"2210_CR17","unstructured":"Baloglou, G.: Personal communication (1999)"},{"key":"2210_CR18","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1007\/s00454-012-9467-8","volume":"49","author":"I B\u00e1r\u00e1ny","year":"2013","unstructured":"B\u00e1r\u00e1ny, I., Blagojevi\u0107, P., Blagojevi\u0107, A.D.: Functions, measures, and equipartitioning convex $$k$$-fans. Discrete Comput. Geom. 49, 382\u2013401 (2013)","journal-title":"Discrete Comput. Geom."},{"key":"2210_CR19","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/s00454-001-0003-5","volume":"25","author":"I B\u00e1r\u00e1ny","year":"2001","unstructured":"B\u00e1r\u00e1ny, I., Matou\u0161ek, J.: Simultaneous partitions of measures by $$k$$-fans. Discrete Comput. Geom. 25, 317\u2013334 (2001)","journal-title":"Discrete Comput. Geom."},{"key":"2210_CR20","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s00454-001-0071-6","volume":"27","author":"I B\u00e1r\u00e1ny","year":"2002","unstructured":"B\u00e1r\u00e1ny, I., Matou\u0161ek, J.: Equipartition of two measures by a 4-fan. Discrete Comput. Geom. 27, 293\u2013301 (2002)","journal-title":"Discrete Comput. Geom."},{"key":"2210_CR21","unstructured":"Barba, L., Pilz, A., Schnider, P.: Sharing a pizza: bisecting masses with two cuts (2019). arXiv:1904.02502v1"},{"key":"2210_CR22","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s00454-004-1151-1","volume":"34","author":"S Bereg","year":"2005","unstructured":"Bereg, S.: Equipartitions of measures by 2-fans. Discrete Comput. Geom. 34, 87\u201396 (2005)","journal-title":"Discrete Comput. Geom."},{"key":"2210_CR23","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/j.comgeo.2008.09.004","volume":"42","author":"S Bereg","year":"2009","unstructured":"Bereg, S.: Orthogonal equipartitions. Discrete Comput. Geom. 42, 305\u2013314 (2009)","journal-title":"Discrete Comput. Geom."},{"key":"2210_CR24","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.comgeo.2005.06.003","volume":"34","author":"S Bereg","year":"2006","unstructured":"Bereg, S., Bose, P., Kirkpatrick, D.: Equitable subdivisions within polygonal regions. Comput. Geom. 34, 20\u201327 (2006)","journal-title":"Comput. Geom."},{"key":"2210_CR25","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/j.comgeo.2014.09.004","volume":"48","author":"S Bereg","year":"2015","unstructured":"Bereg, S., D\u00edaz-B\u00e1\u00f1ez, J.M., Fabila-Monroy, R., P\u00e9rez-Lantero, P., Ram\u00edrez-Vigueras, A., Sakai, T., Urrutia, J., Ventura, I.: On balanced 4-holes in bichromatic point sets. Comput. Geom. 48, 169\u2013179 (2015)","journal-title":"Comput. Geom."},{"key":"2210_CR26","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.comgeo.2012.04.003","volume":"45","author":"S Bereg","year":"2013","unstructured":"Bereg, S., D\u00edaz-B\u00e1\u00f1ez, J.M., Lara, D., P\u00e9rez-Lantero, P., Urrutia, J.: On the coarseness of bicolored point sets. Comput. Geom. 45, 65\u201377 (2013)","journal-title":"Comput. Geom."},{"key":"2210_CR27","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.dam.2014.10.015","volume":"181","author":"S Bereg","year":"2015","unstructured":"Bereg, S., Hurtado, F., Kano, M., Kormand, M., Lara, D., Seara, C., Silveira, R., Urrutia, J., Verbeek, K.: Balanced partitions of 3-colored geometric sets in the plane. Discrete Appl. Math. 181, 21\u201332 (2015)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"2210_CR28","doi-asserted-by":"publisher","first-page":"4","DOI":"10.37236\/10","volume":"19","author":"S Bereg","year":"2012","unstructured":"Bereg, S., Kano, M.: Balanced line for a 3-colored point set in the plane. Electron. J. Comb. 19(1), 4 (2012). (Paper 33)","journal-title":"Electron. J. Comb."},{"key":"2210_CR29","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1007\/s4540010065","volume":"24","author":"S Bespamyatnikh","year":"2000","unstructured":"Bespamyatnikh, S., Kirkpatrick, D., Snoeyink, J.: Generalizing ham sandwich cuts to equitable subdivisioons. Discrete Comput. Geom. 24, 605\u2013622 (2000)","journal-title":"Discrete Comput. Geom."},{"key":"2210_CR30","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1007\/s00454-017-9881-z","volume":"59","author":"A Biniaz","year":"2018","unstructured":"Biniaz, A., Bose, P., Maheshwari, A., Smid, M.: Plane bichromatic trees of low degree. Discrete Comput. Geom. 59, 864\u2013885 (2018)","journal-title":"Discrete Comput. Geom."},{"key":"2210_CR31","doi-asserted-by":"publisher","first-page":"2635","DOI":"10.1016\/j.topol.2007.04.007","volume":"154","author":"PVM Blagojevi\u0107","year":"2007","unstructured":"Blagojevi\u0107, P.V.M., Blagojevi\u0107, A.S.D.: Using equivariant obstruction theory in combinatorial geometry. Topol. Appl. 154, 2635\u20132655 (2007)","journal-title":"Topol. Appl."},{"key":"2210_CR32","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/s00454-017-9959-7","volume":"61","author":"PVM Blagojevi\u0107","year":"2019","unstructured":"Blagojevi\u0107, P.V.M., Rote, G., Steinmeyer, J.K., Ziegler, G.M.: Convex equipartitions of colored point sets. Discrete Comput. Geom. 61, 355\u2013363 (2019)","journal-title":"Discrete Comput. Geom."},{"key":"2210_CR33","doi-asserted-by":"publisher","first-page":"177","DOI":"10.4064\/fm-20-1-177-190","volume":"20","author":"K Borsuk","year":"1933","unstructured":"Borsuk, K.: Drei S\u00e4tze \u00fcber die $$n$$-dimensionale enuklidische Sph\u00e4re. Fundamenta Mathematicase 20, 177\u2013190 (1933)","journal-title":"Fundamenta Mathematicase"},{"key":"2210_CR34","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/s00454-006-1287-2","volume":"37","author":"P Bose","year":"2007","unstructured":"Bose, P., Demaine, E., Hurtado, F., Iacon, J., Langerman, S., Morin, P.: Geodesic ham-sandwich cuts. Discrete Comput. Geom. 37, 325\u2013339 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"2210_CR35","doi-asserted-by":"publisher","first-page":"195","DOI":"10.2307\/3029182","volume":"22","author":"R Buck","year":"1949","unstructured":"Buck, R., Buck, E.: Equipartitioning of convex sets. Math. Mag. 22, 195\u2013198 (1949)","journal-title":"Math. Mag."},{"key":"2210_CR36","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1142\/S0218195918500024","volume":"28","author":"J Buot","year":"2018","unstructured":"Buot, J., Kano, M.: Weight equitable subdivision of red and blue points in the plane. Int. J. Comput. Geom. Appl. 28, 39\u201356 (2018)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"2210_CR37","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/978-1-4614-0110-0_8","volume-title":"Hamiltonian Alternating Paths on Bicolored Double-chains, Thirty Essays on Geometric Graph Theory","author":"J Cibulka","year":"2013","unstructured":"Cibulka, J., Kyn\u010dl, J., M\u00e9sz\u00e1ros, V., Stola\u0159, R., Valtr, P.: Hamiltonian Alternating Paths on Bicolored Double-chains, Thirty Essays on Geometric Graph Theory, pp. 101\u2013119. Springer, Berlin (2013)"},{"key":"2210_CR38","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1016\/j.comgeo.2017.05.009","volume":"68","author":"M Claverol","year":"2018","unstructured":"Claverol, M., Garc\u00eda, A., Garijo, D., Seara, C., Tejel, J.: On Hamiltonian alternating cycles and paths. Comput. Geom. 68, 146\u2013166 (2018)","journal-title":"Comput. Geom."},{"key":"2210_CR39","unstructured":"Claverol, M., Garijo, D., Hurtado, F., Lara, D., Seara, C.: The alternating path problem revisited. In: Proceedings of XV EGC, Sevilla, June 26\u201328, pp. 115\u2013118 (2013)"},{"key":"2210_CR40","first-page":"21","volume":"11","author":"J Czyzowciz","year":"2001","unstructured":"Czyzowciz, J., Hurtado, F., Urrutia, J., Zaguia, N.: On polygons enclosing point sets. Geombinatorics 11, 21\u201328 (2001)","journal-title":"Geombinatorics"},{"key":"2210_CR41","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/S0925-7721(03)00013-0","volume":"26","author":"O Devillers","year":"2003","unstructured":"Devillers, O., Hurtado, F., K\u00e1rolyi, G., Seara, C.: Chromatic variants of the Erd\u0151s\u2013Szekeres theorem on points in convex position. Comput. Geom. 26, 193\u2013208 (2003)","journal-title":"Comput. Geom."},{"key":"2210_CR42","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ipl.2017.02.007","volume":"123","author":"JM D\u00edaz-B\u00e1\u00f1ez","year":"2017","unstructured":"D\u00edaz-B\u00e1\u00f1ez, J.M., Fabila-Monroy, R., Ventura, I.: New results on the coarseness of bicolored point sets. Inf. Process. Lett. 123, 1\u20137 (2017)","journal-title":"Inf. Process. Lett."},{"key":"2210_CR43","first-page":"111","volume-title":"How to Embed a Path onto Two Sets of Points, Graph drawing. Lecture Notes in Computer Science","author":"E Di Giacomo","year":"2006","unstructured":"Di Giacomo, E., Liotta, G., Trotta, F.: How to Embed a Path onto Two Sets of Points, Graph drawing. Lecture Notes in Computer Science, vol. 3843, pp. 111\u2013116. Springer, Berlin (2006)"},{"key":"2210_CR44","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0925-7721(01)00007-4","volume":"19","author":"A Dumitrescu","year":"2001","unstructured":"Dumitrescu, A., Kaye, R.: Matching colored points in the plane: some new results. Comput. Geom. 19, 69\u201385 (2001)","journal-title":"Comput. Geom."},{"key":"2210_CR45","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/S0012-365X(99)00201-0","volume":"211","author":"A Dumitrescu","year":"2000","unstructured":"Dumitrescu, A., Steiger, W.: On a matching problem in the plane. Discrete Math. 211, 183\u2013195 (2000)","journal-title":"Discrete Math."},{"key":"2210_CR46","doi-asserted-by":"publisher","first-page":"1741","DOI":"10.1007\/s00373-012-1221-8","volume":"29","author":"R Fulek","year":"2013","unstructured":"Fulek, R., Keszegh, B., Mor\u00edc, F., Uljarevi\u0107, I.: On polygons excluding point sets. Graphs Combin. 29, 1741\u20131753 (2013)","journal-title":"Graphs Combin."},{"key":"2210_CR47","doi-asserted-by":"crossref","unstructured":"Garijo, D., Garrido, M.A., Grima, C.I., M\u00e1rquez, A., Moreno-Gonz\u00e1lez, A., Portillo, J.R., Reyes, P.,Robles, R., Valenzuela, J.: Monochromatic geometric $$k$$-factors in red-blue sets with white and Steiner points. In: European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009), Electronic Notes Discrete Math., vol. 34, pp. 151\u2013155 (2009)","DOI":"10.1016\/j.endm.2009.07.025"},{"key":"2210_CR48","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.ipl.2013.10.002","volume":"114","author":"D Garijo","year":"2014","unstructured":"Garijo, D., Garrido, M.A., Grima, C.I., M\u00e1rquez, A., Moreno-Gonz\u00e1lez, A., Portillo, J.R., Reyes, P., Robles, R., Valenzuela, J.: Monochromatic geometric $$k$$-factors for bicolored point sets with auxiliary points. Inf. Process. Lett. 114, 19\u201324 (2014)","journal-title":"Inf. Process. Lett."},{"key":"2210_CR49","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.jda.2012.04.012","volume":"16","author":"ED Giacomo","year":"2012","unstructured":"Giacomo, E.D., Grilli, L., Krug, M., Liotta, G., Rutter, I.: Hamiltonian orthogeodesic alternating paths. J. Discrete Algorithms 16, 34\u201352 (2012)","journal-title":"J. Discrete Algorithms"},{"key":"2210_CR50","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1137\/0606010","volume":"6","author":"CH Goldberg","year":"1985","unstructured":"Goldberg, C.H., West, D.B.: Bisection of circle colorings. SIAM J. Algebraic Discrete Methods 6, 93\u2013106 (1985)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"2210_CR51","volume-title":"(Edited): Handbook of discrete and computational geometry","author":"JE Goodman","year":"2004","unstructured":"Goodman, J.E., O\u2019Rourke, J.: (Edited): Handbook of discrete and computational geometry, 2nd edn. Chapman & Hall\/CRC, Boca Raton (2004)","edition":"2"},{"key":"2210_CR52","unstructured":"Grima, C., Hernando, C., Huemer, C., Hurtado, F.: On some partitioning problems for two-colored point sets. In: Proceedings of XIII Encuentros de GDeometr\u00fda Computacional, Zaragoza, Spain (2009)"},{"key":"2210_CR53","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/j.comgeo.2017.05.001","volume":"65","author":"A Holmsen","year":"2017","unstructured":"Holmsen, A., Kyn\u010dl, J., Valculescu, C.: Near equipartitions of colored point sets. Comput. Geom. 65, 35\u201342 (2017)","journal-title":"Comput. Geom."},{"key":"2210_CR54","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/j.comgeo.2006.12.005","volume":"43","author":"M Hoffmann","year":"2010","unstructured":"Hoffmann, M., Speckmann, B., T\u00f3th, C.D.: Pointed binary encompassing trees: simple and optimal. Comput. Geom. 43, 35\u201341 (2010)","journal-title":"Comput. Geom."},{"key":"2210_CR55","doi-asserted-by":"publisher","first-page":"933","DOI":"10.1007\/s00373-013-1320-1","volume":"30","author":"M Hoffmann","year":"2014","unstructured":"Hoffmann, M., T\u00f3th, C.: Vertex-colored encompassing graphs. Graphs Comb. 30, 933\u2013947 (2014)","journal-title":"Graphs Comb."},{"key":"2210_CR56","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004119000380","volume-title":"Bisecting Measures with Hyperplane Arrangements","author":"A Hubard","year":"2019","unstructured":"Hubard, A., Karasev, R.: Bisecting Measures with Hyperplane Arrangements. Cambridge University Press, Cambridge (2019). https:\/\/doi.org\/10.1017\/S0305004119000380"},{"key":"2210_CR57","first-page":"5","volume":"19","author":"C Huemer","year":"2009","unstructured":"Huemer, C., Seara, C.: 36 two-colored points with no empty monochromatic convex fourgons. Geombinatorics 19, 5\u20136 (2009)","journal-title":"Geombinatorics"},{"key":"2210_CR58","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.comgeo.2007.05.006","volume":"39","author":"F Hurtado","year":"2008","unstructured":"Hurtado, F., Kano, M., Rappaport, D., T\u00f3th, C.D.: Encompassing colored planar straight line graphs. Comput. Geom. 39, 14\u201323 (2008)","journal-title":"Comput. Geom."},{"key":"2210_CR59","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s00373-009-0848-6","volume":"25","author":"F Hurtado","year":"2009","unstructured":"Hurtado, F., Merino, C., Oliveros, D., Sakai, T., Urrutia, J., Ventura, I.: On polygons enclosing point sets II. Graphs Comb. 25, 327\u2013339 (2009)","journal-title":"Graphs Comb."},{"key":"2210_CR60","first-page":"129","volume-title":"2-Dimensional Ham-sandwich Theorem for Partitioning into Three Convex Pieces, Discrete and Computational Geometry (Tokyo, 1998), Lecture Notes in Computer Science","author":"H Ito","year":"2000","unstructured":"Ito, H., Uehara, H., Yokoyama, M.: 2-Dimensional Ham-sandwich Theorem for Partitioning into Three Convex Pieces, Discrete and Computational Geometry (Tokyo, 1998), Lecture Notes in Computer Science, vol. 1763, pp. 129\u2013157. Springer, Berlin (2000)"},{"key":"2210_CR61","first-page":"166","volume-title":"On the Maximum Degree of Bipartite Embeddings of Trees in the Plane, Discrete and Computational Geometry (Tokyo, 1998), Lecture Notes in Computer Science","author":"A Kankeo","year":"2000","unstructured":"Kankeo, A.: On the Maximum Degree of Bipartite Embeddings of Trees in the Plane, Discrete and Computational Geometry (Tokyo, 1998), Lecture Notes in Computer Science, vol. 1763, pp. 166\u2013171. Springer, Berlin (2000)"},{"key":"2210_CR62","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/S0925-7721(99)00024-3","volume":"13","author":"A Kaneko","year":"1999","unstructured":"Kaneko, A., Kano, M.: Balanced partitions of two sets of points in the plane. Comput. Geom. 13, 253\u2013261 (1999)","journal-title":"Comput. Geom."},{"key":"2210_CR63","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0166-218X(99)00191-2","volume":"101","author":"A Kaneko","year":"2000","unstructured":"Kaneko, A., Kano, M.: Straight line embeddings of rooted star forests in the plane. Discrete Appl. Math. 101, 167\u2013175 (2000)","journal-title":"Discrete Appl. Math."},{"key":"2210_CR64","first-page":"187","volume-title":"On Paths in a Complete Bipartite Geometric Graph, Discrete and Computational Geometry, Lecture Notes in Computer Science","author":"A Kaneko","year":"2001","unstructured":"Kaneko, A., Kano, M.: On Paths in a Complete Bipartite Geometric Graph, Discrete and Computational Geometry, Lecture Notes in Computer Science, vol. 2098, pp. 187\u2013191. Springer, Berlin (2001)"},{"key":"2210_CR65","first-page":"176","volume-title":"Generalized Balanced Partitions of Two Sets of Points in the Plane, Discrete and Computational Geometry (Tokyo, 2000), Lecture Notes in Computer Science","author":"A Kaneko","year":"2001","unstructured":"Kaneko, A., Kano, M.: Generalized Balanced Partitions of Two Sets of Points in the Plane, Discrete and Computational Geometry (Tokyo, 2000), Lecture Notes in Computer Science, vol. 2098, pp. 176\u2013186. Springer, Berlin (2001)"},{"key":"2210_CR66","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s00454-002-2808-2","volume":"28","author":"A Kaneko","year":"2002","unstructured":"Kaneko, A., Kano, M.: Perfect $$n$$-partitions of convex sets in the plane. Discrete Comput. Geom. 28, 211\u2013222 (2002)","journal-title":"Discrete Comput. Geom."},{"key":"2210_CR67","first-page":"551","volume-title":"Discrete Geometry on Red and Blue Points in the Plane\u2014A Survey, Discrete and Computational Geometry. Algorithms Combination","author":"A Kaneko","year":"2003","unstructured":"Kaneko, A., Kano, M.: Discrete Geometry on Red and Blue Points in the Plane\u2014A Survey, Discrete and Computational Geometry. Algorithms Combination, vol. 25, pp. 551\u2013570. Springer, Berlin (2003)"},{"key":"2210_CR68","first-page":"108","volume-title":"A Balanced Interval of Two Sets of Points on a Line, Combinatorial Geometry and Graph Theory, Lecture Notes in Computer Science","author":"A Kaneko","year":"2005","unstructured":"Kaneko, A., Kano, M.: A Balanced Interval of Two Sets of Points on a Line, Combinatorial Geometry and Graph Theory, Lecture Notes in Computer Science, vol. 3330, pp. 108\u2013112. Springer, Berlin (2005)"},{"key":"2210_CR69","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1142\/S0218195905001671","volume":"15","author":"A Kaneko","year":"2005","unstructured":"Kaneko, A., Kano, M.: Semi-balanced partition of two sets of points and embedding of rooted forests Internat. J. Comput. Geom. Appl. 15, 229\u2013238 (2005)","journal-title":"J. Comput. Geom. Appl."},{"key":"2210_CR70","first-page":"99","volume-title":"Path Coverings of Two Sets of Points in the Plane, Towards a Theory of Geometric Graphs, Contemporary Mathematics","author":"A Kaneko","year":"2004","unstructured":"Kaneko, A., Kano, M., Suzuki, K.: Path Coverings of Two Sets of Points in the Plane, Towards a Theory of Geometric Graphs, Contemporary Mathematics, vol. 342, pp. 99\u2013111. American Mathematical Society, Providence (2004)"},{"key":"2210_CR71","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1142\/S021819590000005X","volume":"10","author":"A Kaneko","year":"2000","unstructured":"Kaneko, A., Kano, M., Yoshimoto, K.: Alternating Hamiltonian cycles with minimum number of crossings in the plane. Int. J. Comput. Geom. Appl. 10, 73\u201378 (2000)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"2210_CR72","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.comgeo.2017.06.012","volume":"68","author":"M Kano","year":"2018","unstructured":"Kano, M., Kyn\u010dl, J.: The hamburger theorem. Comput. Geom. 68, 167\u2013173 (2018)","journal-title":"Comput. Geom."},{"key":"2210_CR73","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/j.ipl.2004.12.003","volume":"93","author":"M Kano","year":"2005","unstructured":"Kano, M., Merino, C., Urrutia, J.: On plane spanning trees and cycles of multicolored point sets with few intersections. Inf. Process. Lett. 93, 301\u2013306 (2005)","journal-title":"Inf. Process. Lett."},{"key":"2210_CR74","first-page":"96","volume-title":"Properly Colored Geometric Matchings and 3-trees Without Crossings on Multicolored Points in the Plane, Discrete and Computational Geometry and Graphs, Lecture Notes in Computer Science","author":"M Kano","year":"2014","unstructured":"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, Lecture Notes in Computer Science, vol. 8845, pp. 96\u2013111. Springer, Cham (2014)"},{"key":"2210_CR75","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/978-1-4614-0110-0_18","volume-title":"Discrete Geometry on Red and Blue Points in the Plane Lattice Thirty Essays on Geometric Graph Theory","author":"M Kano","year":"2013","unstructured":"Kano, M., Suzuki, K.: Discrete Geometry on Red and Blue Points in the Plane Lattice Thirty Essays on Geometric Graph Theory, pp. 355\u2013369. Springer, Berlin (2013)"},{"key":"2210_CR76","unstructured":"Kano, M., Suzuki, K.: Personal communication (2014)"},{"key":"2210_CR77","first-page":"79","volume-title":"General Balanced Subdivision of Two Sets of Points in the Plane, Discrete Geometry, Combinatorics and Graph Theory, Lecture Notes in Computer Science","author":"M Kano","year":"2007","unstructured":"Kano, M., Uno, M.: General Balanced Subdivision of Two Sets of Points in the Plane, Discrete Geometry, Combinatorics and Graph Theory, Lecture Notes in Computer Science, vol. 4381, pp. 79\u201387. Springer, Berlin (2007)"},{"key":"2210_CR78","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1142\/S0218195910003426","volume":"20","author":"M Kano","year":"2010","unstructured":"Kano, M., Uno, M.: Balanced subdivision with boundary condition of two sets of points in the plane. Int. J. Comput. Geom. Appl. 20, 527\u2013541 (2010)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"2210_CR79","unstructured":"Karasev, R.N.: Equipartition of several measures (2010). arXiv:1011.4762v7"},{"key":"2210_CR80","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s10711-013-9879-5","volume":"170","author":"RN Karasev","year":"2014","unstructured":"Karasev, R.N., Hubard, A., Aronov, B.: Convex equipartition: the spicy chicken theorem. Geom. Dedicata 170, 263\u2013279 (2014)","journal-title":"Geom. Dedicata"},{"key":"2210_CR81","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1007\/s11856-016-1303-z","volume":"212","author":"RN Karasev","year":"2016","unstructured":"Karasev, R.N., Rold\u00e1n-Pensado, E., Sober\u00f3n, P.: Measure partitions using hyperplanes with fixed directions. Isr. J. Math. 212, 705\u2013728 (2016)","journal-title":"Isr. J. Math."},{"key":"2210_CR82","unstructured":"Kleitman, D.J., Pinchasi, R.: A note on the number of bichromatic lines. http:\/\/www2.math.technion.ac.ilroom\/ps_files\/KP_bichnum.pdf\/. Accessed 2003"},{"key":"2210_CR83","doi-asserted-by":"crossref","unstructured":"Koshelev, V.A.: On Erd\u0151s\u2013Szekeres problem and related problems (2009). arXiv:0910.2700v1","DOI":"10.1016\/j.endm.2009.07.074"},{"key":"2210_CR84","unstructured":"Kyn\u010dl, J.: Personal communication (2014)"},{"key":"2210_CR85","doi-asserted-by":"publisher","first-page":"4315","DOI":"10.1016\/j.disc.2007.08.013","volume":"308","author":"J Kyn\u010dl","year":"2008","unstructured":"Kyn\u010dl, J., Pach, J., T\u00f3th, G.: Long alternating paths in bicolored point ets. Discrete Math. 308, 4315\u20134321 (2008)","journal-title":"Discrete Math."},{"key":"2210_CR86","first-page":"113","volume-title":"Spanning Trees of Mutlicolored Point Sets with Few Intersections, Combinatorial Geometry and Graph Theory, Lecture Notes in Computer Science","author":"J Leanos","year":"2005","unstructured":"Leanos, J., Merino, C., Slazar, G., Urrutia, J.: Spanning Trees of Mutlicolored Point Sets with Few Intersections, Combinatorial Geometry and Graph Theory, Lecture Notes in Computer Science, vol. 3330, pp. 113\u2013122. Springer, Berlin (2005)"},{"key":"2210_CR87","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/BF02574017","volume":"11","author":"C-Y Lo","year":"1994","unstructured":"Lo, C.-Y., Matou\u0161ek, J., Steiger, W.: Algorithms for ham-sandwich cuts. Discrete Comput. Geom. 11, 433\u2013452 (1994)","journal-title":"Discrete Comput. Geom."},{"key":"2210_CR88","volume-title":"Using the Borsuk\u2013Ulam Theorem","author":"J Matou\u0161ek","year":"2003","unstructured":"Matou\u0161ek, J.: Using the Borsuk\u2013Ulam Theorem. Springer, Berlin (2003)"},{"key":"2210_CR89","first-page":"837","volume":"14","author":"TS Motzkin","year":"1967","unstructured":"Motzkin, T.S.: Nonmixed connecting lines, Abstract 67T 605. Not. Am. Math. Soc. 14, 837 (1967)","journal-title":"Not. Am. Math. Soc."},{"key":"2210_CR90","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1016\/0196-6774(85)90011-2","volume":"6","author":"N Megiddo","year":"1985","unstructured":"Megiddo, N.: Partitioning with two lines in the plane. J. Algorithms 6, 430\u2013433 (1985)","journal-title":"J. Algorithms"},{"key":"2210_CR91","doi-asserted-by":"publisher","first-page":"1791","DOI":"10.1016\/j.disc.2006.03.035","volume":"306","author":"C Merino","year":"2006","unstructured":"Merino, C., Salazar, G., Urrutia, J.: On the length of longest alternating paths for multicolores point sets in convex position. Discrete Math. 306, 1791\u20131797 (2006)","journal-title":"Discrete Math."},{"key":"2210_CR92","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/s00373-004-0606-8","volume":"21","author":"C Merino","year":"2005","unstructured":"Merino, C., Salazar, G., Urrutia, J.: On the Intersection number of matchings and minimum weight perfect matchings of multicolored point sets. Graphs Comb. 21, 333\u2013341 (2005)","journal-title":"Graphs Comb."},{"key":"2210_CR93","doi-asserted-by":"publisher","first-page":"805","DOI":"10.1007\/s00454-010-9253-4","volume":"44","author":"D Orden","year":"2010","unstructured":"Orden, D., Ramos, P., Salazar, G.: The number of generalized balanced lines. Discrete Comput. Geom. 44, 805\u2013811 (2010)","journal-title":"Discrete Comput. Geom."},{"key":"2210_CR94","first-page":"167","volume-title":"Geometric Graph Theory, Surveys in Combinatorics, 1999 (Canterbury), London Mathematical Society Lecture Note Series","author":"J Pach","year":"1999","unstructured":"Pach, J.: Geometric Graph Theory, Surveys in Combinatorics, 1999 (Canterbury), London Mathematical Society Lecture Note Series, vol. 267, pp. 167\u2013200. Cambridge University Press, Cambridge (1999)"},{"key":"2210_CR95","volume-title":"Combinatorial Geometry. Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley-Interscience Publication","author":"J Pach","year":"1995","unstructured":"Pach, J., Agarwal, P.K.: Combinatorial Geometry. Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley-Interscience Publication. Wiley, New York (1995)"},{"key":"2210_CR96","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1006\/jcta.1999.3047","volume":"90","author":"J Pach","year":"2000","unstructured":"Pach, J., Pinchasi, R.: Bichromatic lines with few points. J. Comb. Theory Ser. A 90, 326\u2013335 (2000)","journal-title":"J. Comb. Theory Ser. A"},{"key":"2210_CR97","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1007\/s00454-001-0013-3","volume":"25","author":"J Pach","year":"2001","unstructured":"Pach, J., Pinchasi, R.: On the number of balanced lines. Discrete Comput. Geom. 25, 611\u2013628 (2001)","journal-title":"Discrete Comput. Geom."},{"key":"2210_CR98","first-page":"195","volume-title":"Monochromatic Empty Triangles in Two-colored Point Sets, Geometry, Games, Graphs and Education: the Joe Malkevitch Festschrift","author":"J Pach","year":"2008","unstructured":"Pach, J., T\u00f3th, G.: Monochromatic Empty Triangles in Two-colored Point Sets, Geometry, Games, Graphs and Education: the Joe Malkevitch Festschrift, pp. 195\u2013198. Comap Inc, Bedford (2008)"},{"key":"2210_CR99","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/s00454-009-9154-6","volume":"43","author":"GB Purdy","year":"2010","unstructured":"Purdy, G.B., Smith, J.W.: Bichromatic and equichromatic lines in $${\\mathbb{C}}^2$$ and $${\\mathbb{R}}^2$$. Discrete Comput. Geom. 43, 563\u2013576 (2010)","journal-title":"Discrete Comput. Geom."},{"key":"2210_CR100","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/s003730200011","volume":"18","author":"T Sakai","year":"2002","unstructured":"Sakai, T.: Balanced convex partitions of measures in $${\\mathbb{R}}^{2}$$. Graphs Comb. 18, 169\u2013192 (2002)","journal-title":"Graphs Comb."},{"key":"2210_CR101","first-page":"789","volume-title":"Balanced Lines, Halving Triangles, and the Generalized Lower Bound Theorem, Discrete and Computational Geometry. Algorithms Combination","author":"M Sharir","year":"2003","unstructured":"Sharir, M., Welzl, E.: Balanced Lines, Halving Triangles, and the Generalized Lower Bound Theorem, Discrete and Computational Geometry. Algorithms Combination, vol. 25, pp. 789\u2013797. Springer, Berlin (2003)"},{"key":"2210_CR102","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1112\/S0025579311001914","volume":"58","author":"P Sober\u00f3n","year":"2012","unstructured":"Sober\u00f3n, P.: Balanced convex partitions of measures in $${\\mathbb{R}}^d$$. Mathematika 58, 71\u201376 (2012)","journal-title":"Mathematika"},{"key":"2210_CR103","doi-asserted-by":"publisher","first-page":"245","DOI":"10.4064\/fm-33-1-245-263","volume":"33","author":"H Steinhaus","year":"1945","unstructured":"Steinhaus, H.: Sur la division des ensembles de l\u2019espace par les plans et des ensembles plans par les cercles. Fundam. Math. 33, 245\u2013263 (1945)","journal-title":"Fundam. Math."},{"key":"2210_CR104","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1215\/S0012-7094-42-00925-6","volume":"9","author":"AH Stone","year":"1942","unstructured":"Stone, A.H., Tukey, J.W.: Generalized \u201csandwich\u201d theorems. Duke Math. J. 9, 356\u2013359 (1942)","journal-title":"Duke Math. J."},{"key":"2210_CR105","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/0020-0190(96)00124-X","volume":"59","author":"S Tokunaga","year":"1996","unstructured":"Tokunaga, S.: Intersection number of two connected geometric graphs. Inf. Process. Lett. 59, 331\u2013333 (1996)","journal-title":"Inf. Process. Lett."},{"key":"2210_CR106","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1587\/transfun.E92.A.502","volume":"E92\u2013A","author":"M Uno","year":"2009","unstructured":"Uno, M., Kawano, T., Kano, M.: Bisections of two sets of points in the plane lattice. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E92\u2013A, 502\u2013507 (2009)","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"2210_CR107","unstructured":"\u017divaljevi\u0107, R.T.: Combinatorics and topology of partitions of spherical measures by 2 and 3 fans (2002). arXiv:math\/0203028v2"},{"key":"2210_CR108","volume-title":"Handbook of Discrete and Computational Geometry, Discrete Mathematics and its Applications","author":"RT \u017divaljevi\u0107","year":"2004","unstructured":"\u017divaljevi\u0107, R.T.: Topological methods. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, Discrete Mathematics and its Applications, 2nd edn. Chapman & Hall\/CRC, Boca Raton (2004)","edition":"2"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-020-02210-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-020-02210-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-020-02210-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,15]],"date-time":"2021-07-15T23:46:17Z","timestamp":1626392777000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-020-02210-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,16]]},"references-count":108,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["2210"],"URL":"https:\/\/doi.org\/10.1007\/s00373-020-02210-8","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,16]]},"assertion":[{"value":"7 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 May 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}