{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:25Z","timestamp":1740109585943,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,6,7]],"date-time":"2022-06-07T00:00:00Z","timestamp":1654560000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,6,7]],"date-time":"2022-06-07T00:00:00Z","timestamp":1654560000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100008332","name":"Graz University of Technology","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100008332","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Let <jats:italic>S<\/jats:italic> be a set of <jats:italic>n<\/jats:italic> points in general position in the plane, and let <jats:inline-formula><jats:alternatives><jats:tex-math>$$X_{k,\\ell }(S)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>X<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mi>k<\/mml:mi>\n                        <mml:mo>,<\/mml:mo>\n                        <mml:mi>\u2113<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>S<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> be the number of convex <jats:italic>k<\/jats:italic>-gons with vertices in <jats:italic>S<\/jats:italic> that have exactly\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u2113<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> points of <jats:italic>S<\/jats:italic> in their interior. We prove several equalities for the numbers <jats:inline-formula><jats:alternatives><jats:tex-math>$$X_{k,\\ell }(S)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>X<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mi>k<\/mml:mi>\n                        <mml:mo>,<\/mml:mo>\n                        <mml:mi>\u2113<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>S<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This problem is related to the Erd\u0151s\u2013Szekeres theorem. Some of the obtained equations also extend known equations for the numbers of empty convex polygons to polygons with interior points. Analogous results for higher dimension are shown as well.<\/jats:p>","DOI":"10.1007\/s00454-022-00395-8","type":"journal-article","created":{"date-parts":[[2022,6,7]],"date-time":"2022-06-07T15:09:57Z","timestamp":1654614597000},"page":"448-476","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Weighted Sums of Numbers of Convex Polygons in Point Sets"],"prefix":"10.1007","volume":"68","author":[{"given":"Clemens","family":"Huemer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Deborah","family":"Oliveros","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pablo","family":"P\u00e9rez-Lantero","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ferran","family":"Torra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7166-4467","authenticated-orcid":false,"given":"Birgit","family":"Vogtenhuber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,6,7]]},"reference":[{"issue":"3","key":"395_CR1","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/PL00009469","volume":"22","author":"C Ahrens","year":"1999","unstructured":"Ahrens, C., Gordon, G., McMahon, E.W.: Convexity and the beta invariant. Discrete Comput. Geom. 22(3), 411\u2013424 (1999)","journal-title":"Discrete Comput. Geom."},{"key":"395_CR2","doi-asserted-by":"crossref","unstructured":"Aichholzer, O., Balko, M., Hackl, Th., Kyn\u010dl, J., Parada, I., Scheucher, M., Valtr, P., Vogtenhuber, B.: A superlinear lower bound on the number of $$5$$-holes. J. Comb. Theory Ser. A 173, # 105236 (2020)","DOI":"10.1016\/j.jcta.2020.105236"},{"issue":"1","key":"395_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00454-007-1325-8","volume":"38","author":"O Aichholzer","year":"2007","unstructured":"Aichholzer, O., Garc\u00eda, J., Orden, D., Ramos, P.: New lower bounds for the number of $$(\\le k)$$-edges and the rectilinear crossing number of $$K_n$$. Discrete Comput. Geom. 38(1), 1\u201314 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"395_CR4","doi-asserted-by":"crossref","unstructured":"Andrzejak, A., Aronov, B., Har-Peled, S., Seidel, R., Welzl, E.: Results on $$k$$-sets and $$j$$-facets via continuous motion. In: 14th Annual Symposium on Computational Geometry (Minneapolis 1998), pp. 192\u2013199. ACM, New York (1998)","DOI":"10.1145\/276884.276906"},{"issue":"2","key":"395_CR5","first-page":"243","volume":"41","author":"I B\u00e1r\u00e1ny","year":"2004","unstructured":"B\u00e1r\u00e1ny, I., Valtr, P.: Planar point sets with a small number of empty convex polygons. Stud. Sci. Math. Hung. 41(2), 243\u2013266 (2004)","journal-title":"Stud. Sci. Math. Hung."},{"issue":"4","key":"395_CR6","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1016\/j.orl.2011.04.008","volume":"39","author":"C Bautista-Santiago","year":"2011","unstructured":"Bautista-Santiago, C., D\u00edaz-B\u00e1\u00f1ez, J.M., Lara, D., P\u00e9rez-Lantero, P., Urrutia, J., Ventura, I.: Computing optimal islands. Oper. Res. Lett. 39(4), 246\u2013251 (2011)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"395_CR7","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0012-365X(90)90232-7","volume":"91","author":"A Bialostocki","year":"1991","unstructured":"Bialostocki, A., Dierker, P., Voxman, B.: Some notes on the Erd\u0151s\u2013Szekeres theorem. Discrete Math. 91(3), 231\u2013238 (1991)","journal-title":"Discrete Math."},{"issue":"2","key":"395_CR8","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00454-017-9931-6","volume":"59","author":"F Duque","year":"2018","unstructured":"Duque, F., Fabila-Monroy, R., Hidalgo-Toscano, C.: Point sets with small integer coordinates and no large convex polygons. Discrete Comput. Geom. 59(2), 461\u2013476 (2018)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"395_CR9","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/BF00149365","volume":"19","author":"PH Edelman","year":"1985","unstructured":"Edelman, P.H., Jamison, R.E.: The theory of convex geometries. Geom. Ded. 19(3), 247\u2013270 (1985)","journal-title":"Geom. Ded."},{"issue":"1","key":"395_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/PL00009483","volume":"23","author":"PH Edelman","year":"2000","unstructured":"Edelman, P.H., Reiner, V.: Counting the interior points of a point configuration. Discrete Comput. Geom. 23(1), 1\u201313 (2000)","journal-title":"Discrete Comput. Geom."},{"key":"395_CR11","doi-asserted-by":"crossref","unstructured":"Erd\u0151s, P.: Some old and new problems in combinatorial geometry. In: Convexity and Graph Theory (Jerusalem 1981). North-Holland Mathematical Studies, vol. 87. Annals of Discrete Mathematics, vol. 20, pp. 129\u2013136. North-Holland, Amsterdam (1984)","DOI":"10.1016\/S0304-0208(08)72816-0"},{"key":"395_CR12","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1080\/00029890.1973.11993230","volume":"80","author":"P Erd\u0151s","year":"1973","unstructured":"Erd\u0151s, P., Guy, R.K.: Crossing number problems. Am. Math. Monthly 80, 52\u201358 (1973)","journal-title":"Am. Math. Monthly"},{"key":"395_CR13","first-page":"463","volume":"2","author":"P Erd\u00f6s","year":"1935","unstructured":"Erd\u00f6s, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463\u2013470 (1935)","journal-title":"Compos. Math."},{"key":"395_CR14","unstructured":"Erd\u0151s, P., Szekeres, G.: On some extremum problems in elementary geometry. Ann. Univ. Sci. Budapest. E\u00f6tv\u00f6s Sect. Math. 3-4, 53\u201362 (1960\/1961)"},{"key":"395_CR15","doi-asserted-by":"crossref","unstructured":"Fabila-Monroy, R., Huemer, C.: Covering islands in plane point sets. In: Computational Geometry (Alcal\u00e1 de Henares 2011). Lecture Notes in Computer Science, vol. 7579, pp. 220\u2013225. Springer, Cham (2011)","DOI":"10.1007\/978-3-642-34191-5_21"},{"key":"395_CR16","doi-asserted-by":"crossref","unstructured":"Garc\u00eda, A.: A note on the number of empty triangles. In: Computational Geometry (Alcal\u00e1 de Henares 2011). Lecture Notes in Computer Science, vol. 7579, pp. 249\u2013257. Springer, Cham (2011)","DOI":"10.1007\/978-3-642-34191-5_24"},{"issue":"1\u20133","key":"395_CR17","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s00454-007-9018-x","volume":"39","author":"T Gerken","year":"2008","unstructured":"Gerken, T.: Empty convex hexagons in planar point sets. Discrete Comput. Geom. 39(1\u20133), 239\u2013272 (2008)","journal-title":"Discrete Comput. Geom."},{"issue":"5","key":"395_CR18","first-page":"116","volume":"33","author":"H Harborth","year":"1978","unstructured":"Harborth, H.: Konvexe F\u00fcnfecke in ebenen Punktmengen. Elem. Math. 33(5), 116\u2013118 (1978)","journal-title":"Elem. Math."},{"issue":"4","key":"395_CR19","doi-asserted-by":"publisher","first-page":"482","DOI":"10.4153\/CMB-1983-077-8","volume":"26","author":"JD Horton","year":"1983","unstructured":"Horton, J.D.: Sets with no empty convex $$7$$-gons. Can. Math. Bull. 26(4), 482\u2013484 (1983)","journal-title":"Can. Math. Bull."},{"issue":"1","key":"395_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/aima.1999.1831","volume":"147","author":"DA Klain","year":"1999","unstructured":"Klain, D.A.: An Euler relation for valuations on polytopes. Adv. Math. 147(1), 1\u201334 (1999)","journal-title":"Adv. Math."},{"key":"395_CR21","volume-title":"Chebyshev Polynomials","author":"JC Mason","year":"2003","unstructured":"Mason, J.C., Handscomb, D.C.: Chebyshev Polynomials. Chapman\u00a0 &\u00a0Hall\/CRC, Boca Raton (2003)"},{"issue":"4","key":"395_CR22","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1090\/S0273-0979-00-00877-6","volume":"37","author":"W Morris","year":"2000","unstructured":"Morris, W., Soltan, V.: The Erd\u0151s\u2013Szekeres problem on points in convex position\u2014a survey. Bull. Am. Math. Soc. 37(4), 437\u2013458 (2000)","journal-title":"Bull. Am. Math. Soc."},{"issue":"2","key":"395_CR23","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/s00454-007-1343-6","volume":"38","author":"CM Nicol\u00e1s","year":"2007","unstructured":"Nicol\u00e1s, C.M.: The empty hexagon theorem. Discrete Comput. Geom. 38(2), 389\u2013397 (2007)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"395_CR24","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/s00454-002-2829-x","volume":"29","author":"M Overmars","year":"2003","unstructured":"Overmars, M.: Finding sets of points without empty convex $$6$$-gons. Discrete Comput. Geom. 29(1), 153\u2013158 (2003)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"395_CR25","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/j.jcta.2005.03.007","volume":"113","author":"R Pinchasi","year":"2006","unstructured":"Pinchasi, R., Radoi\u010di\u0107, R., Sharir, M.: On empty convex polygons in a planar point set. J. Comb. Theory Ser. A 113(3), 385\u2013419 (2006)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"24","key":"395_CR26","doi-asserted-by":"publisher","first-page":"3130","DOI":"10.1016\/j.disc.2007.03.052","volume":"307","author":"MZ Spivey","year":"2007","unstructured":"Spivey, M.Z.: Combinatorial sums and finite differences. Discrete Math. 307(24), 3130\u20133146 (2007)","journal-title":"Discrete Math."},{"key":"395_CR27","unstructured":"Sprugnoli, R.: Riordan array proofs of identities in Gould\u2019s book (2006). http:\/\/www.dsi.unifi.it\/resp\/GouldBK.pdf"},{"issue":"4","key":"395_CR28","doi-asserted-by":"publisher","first-page":"1047","DOI":"10.1090\/jams\/869","volume":"30","author":"A Suk","year":"2017","unstructured":"Suk, A.: On the Erd\u0151s\u2013Szekeres convex polygon problem. J. Am. Math. Soc. 30(4), 1047\u20131053 (2017)","journal-title":"J. Am. Math. Soc."},{"key":"395_CR29","unstructured":"Torra Clotet, F.: Combinatorial Properties of Convex Polygons in Point Sets Title. MSc thesis, Universitat Polit\u00e8cnica de Catalunya (2019). https:\/\/upcommons.upc.edu\/handle\/2117\/166052"},{"key":"395_CR30","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1112\/jlms\/s1-41.1.123","volume":"41","author":"H Tverberg","year":"1966","unstructured":"Tverberg, H.: A generalization of Radon\u2019s theorem. J. Lond. Math. Soc. 41, 123\u2013128 (1966)","journal-title":"J. Lond. Math. Soc."},{"key":"395_CR31","unstructured":"Valtr, P.: On empty pentagons and hexagons in planar point sets. In: 18th Computing: Australasian Theory Symposium (Melbourne 2012), pp. 47\u201348. Australian Computer Society, Darlinghurst (2012)"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00395-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-022-00395-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00395-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,23]],"date-time":"2022-08-23T16:06:23Z","timestamp":1661270783000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-022-00395-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,7]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["395"],"URL":"https:\/\/doi.org\/10.1007\/s00454-022-00395-8","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2022,6,7]]},"assertion":[{"value":"18 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 March 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 March 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}