{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T03:06:36Z","timestamp":1787367996992,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>We consider a variation of a problem stated by Erd\u0151s and Szekeres in 1935 about the existence of a number $f^{\\mathrm{ES}}(k)$ such that any set S of at least $f^{\\mathrm{ES}}(k)$ points in general position in the plane has a subset of k points that are the vertices of a convex k-gon. In our setting the points of S are colored, and we say that a (not necessarily convex) spanned polygon is monochromatic if all its vertices have the same color. Moreover, a polygon is called empty if it does not contain any points of S in its interior. We show that any sufficiently large bichromatic set of points in $\\mathbb{R}^2$ in general position determines at least one empty, monochromatic quadrilateral (and thus linearly many).<\/jats:p>","DOI":"10.1137\/090767947","type":"journal-article","created":{"date-parts":[[2010,1,15]],"date-time":"2010-01-15T18:09:05Z","timestamp":1263578945000},"page":"2147-2155","source":"Crossref","is-referenced-by-count":15,"title":["Large Bichromatic Point Sets Admit Empty Monochromatic 4-Gons"],"prefix":"10.1137","volume":"23","author":[{"given":"Oswin","family":"Aichholzer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Hackl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Clemens","family":"Huemer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ferran","family":"Hurtado","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Birgit","family":"Vogtenhuber","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,1,15]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.07.002"},{"key":"R2","unstructured":"O. Aichholzer, R. Fabila-Monroy, D. Flores-Pe\u00f1aloza, T. Hackl, C. Huemer, and J. Urrutia,\n                      Empty monochromatic triangles\n                      , in Proceedings of the 20th Canadian Conference on Computational Geometry, Montreal, Quebec, Canada, 2008, pp. 75\u201378."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"O. Aichholzer, T. Hackl, M. Hoffmann, A. Pilz, G. Rote, B. Speckmann, and B. Vogtenhuber,\n                      Plane graphs with parity constraints\n                      , in Proceedings of the 11th International Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Comput. Sci. 5664, Springer, Berlin, New York, 2009, pp. 13\u201324.","DOI":"10.1007\/978-3-642-03367-4_2"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"O. Aichholzer, T. Hackl, C. Huemer, F. Hurtado, and B. Vogtenhuber,\n                      Large bichromatic point sets admit empty monochromatic 4-gons\n                      , in Proceedings of the 25th European Workshop on Computational Geometry, Brussels, Belgium, 2009, pp. 133\u2013136.","DOI":"10.1137\/090767947"},{"key":"R5","first-page":"5","author":"Brass P.","year":"2004","journal-title":"Geombinatorics"},{"key":"R6","unstructured":"P. Brass, W. Moser, and J. Pach,\n                      Research Problems in Discrete Geometry\n                      , Springer, Berlin, New York, 2005."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(03)00013-0"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.2307\/2319261"},{"key":"R9","first-page":"463","volume":"2","author":"Erd\u0151s P.","year":"1935","journal-title":"Compositio Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0010-437X","issn-type":"print"},{"key":"R10","first-page":"53","author":"Friedmann E.","year":"2004","journal-title":"Geombinatorics"},{"key":"R11","unstructured":"F. Hurtado,\n                      Open problem session\n                      , 21st European Workshop on Computational Geometry, Eindhoven, The Netherlands, 2005."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-007-9018-x"},{"key":"R13","first-page":"116","volume":"33","author":"Harborth H.","year":"1978","journal-title":"Elem. Math."},{"key":"R14","unstructured":"P. Hoffmann,\n                      The Man Who Loved Only Numbers\n                      , Hyperion, New York, 1998."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1983-077-8"},{"key":"R16","first-page":"5","author":"Huemer C.","year":"2009","journal-title":"Geombinatorics"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"J. Pach,\n                      On simplices embracing a point,\n                      invited talk, Topological & Geometric Graph Theory (TGGT), Paris, France, 2008, p. 97.","DOI":"10.1016\/j.endm.2008.06.019"},{"key":"R18","unstructured":"J. Pach and G. T\u00f3th,\n                      Monochromatic empty triangles in two-colored point sets\n                      , in Geometry, Games, Graphs and Education: The Joe Malkevitch Festschrift, COMAP, Bedford, MA, 2008, pp. 195\u2013198."},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-007-1343-6"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-002-2829-x"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1017\/S144618110000300X"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-007-0717-0"},{"key":"R23","unstructured":"J. Urrutia,\n                      Coloraciones, tetraedralizaciones, y tetraedros vacios en coloraciones de conjuntos de puntos en $R^3$\n                      , in Proceedings of the X Encuentros de Geometria Computacional, Sevilla, Spain, 2003, pp. 95\u2013100."},{"key":"R24","doi-asserted-by":"crossref","unstructured":"P. Valtr,\n                      On empty hexagons\n                      , in Surveys on Discrete and Computational Geometry, Twenty Years Later, J. E. Goodman, J. Pach, and R. Pollack, eds., AMS, New York, 2008, pp. 433\u2013441.","DOI":"10.1090\/conm\/453\/08809"},{"key":"R25","first-page":"32","author":"Van Gulik R.","year":"2005","journal-title":"Geombinatorics"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090767947","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:23:52Z","timestamp":1787322232000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090767947"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090767947"],"URL":"https:\/\/doi.org\/10.1137\/090767947","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}