{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:32Z","timestamp":1740109592912,"version":"3.37.3"},"reference-count":9,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,10,12]],"date-time":"2022-10-12T00:00:00Z","timestamp":1665532800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,10,12]],"date-time":"2022-10-12T00:00:00Z","timestamp":1665532800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"publisher","award":["LP2017-19\/2017"],"award-info":[{"award-number":["LP2017-19\/2017"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003549","name":"Hungarian Scientific Research Fund","doi-asserted-by":"crossref","award":["K 116769","K 123696","FK 132060"],"award-info":[{"award-number":["K 116769","K 123696","FK 132060"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"crossref"}]},{"name":"New National Excellence Program of the Ministry of Innovation and Technology, Hungary","award":["UNKP-20-5"],"award-info":[{"award-number":["UNKP-20-5"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>What is the maximum number of intersections of the boundaries of a simple <jats:italic>m<\/jats:italic>-gon and a simple <jats:italic>n<\/jats:italic>-gon? This is a basic question in combinatorial geometry, and the answer is easy if at least one of <jats:italic>m<\/jats:italic> and <jats:italic>n<\/jats:italic> is even: If both <jats:italic>m<\/jats:italic> and <jats:italic>n<\/jats:italic> are even, then every pair of sides may cross and so the answer is <jats:italic>mn<\/jats:italic>. If exactly one polygon, say the <jats:italic>n<\/jats:italic>-gon, has an odd number of sides, it can intersect each side of the <jats:italic>m<\/jats:italic>-gon polygon at most <jats:inline-formula><jats:alternatives><jats:tex-math>$$n-1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> times; hence there are at most <jats:inline-formula><jats:alternatives><jats:tex-math>$$mn-m$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mi>m<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> intersections. It is not hard to construct examples that meet these bounds. If both <jats:italic>m<\/jats:italic> and <jats:italic>n<\/jats:italic> are odd, the best known construction has <jats:inline-formula><jats:alternatives><jats:tex-math>$$mn-(m+n)+3$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mn>3<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> intersections, and it is conjectured that this is the maximum. However, the best known upper bound is only <jats:inline-formula><jats:alternatives><jats:tex-math>$$mn-(m + \\lceil {n}\/{6} \\rceil )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mo>\u2308<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mn>6<\/mml:mn>\n                    <mml:mo>\u2309<\/mml:mo>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, for <jats:inline-formula><jats:alternatives><jats:tex-math>$$m \\ge n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We prove a new upper bound of <jats:inline-formula><jats:alternatives><jats:tex-math>$$mn-(m+n)+C$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>C<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for some constant\u00a0<jats:italic>C<\/jats:italic>, which is optimal apart from the value of\u00a0<jats:italic>C<\/jats:italic>.<\/jats:p>","DOI":"10.1007\/s00454-022-00438-0","type":"journal-article","created":{"date-parts":[[2022,10,12]],"date-time":"2022-10-12T21:02:50Z","timestamp":1665608570000},"page":"1049-1077","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons"],"prefix":"10.1007","volume":"68","author":[{"given":"Eyal","family":"Ackerman","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3839-5103","authenticated-orcid":false,"given":"Bal\u00e1zs","family":"Keszegh","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0351-5945","authenticated-orcid":false,"given":"G\u00fcnter","family":"Rote","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,12]]},"reference":[{"key":"438_CR1","unstructured":"Ackerman, E., Keszegh, B., Rote, G.: An almost optimal bound on the number of intersections of two simple polygons. In: 36th International Symposium on Computational Geometry. Leibniz Int. Proc. Inform., vol. 164, #\u00a01. Leibniz-Zent. Inform., Wadern (2020)"},{"issue":"2","key":"438_CR2","first-page":"217","volume":"44","author":"J \u010cern\u00fd","year":"2003","unstructured":"\u010cern\u00fd, J., K\u00e1ra, J., Kr\u00e1l\u2019, D., Podbrdsk\u00fd, P., Sot\u00e1kov\u00e1, M., \u0160\u00e1mal, R.: On the number of intersections of two polygons. Comment. Math. Univ. Carolin. 44(2), 217\u2013228 (2003)","journal-title":"Comment. Math. Univ. Carolin."},{"key":"438_CR3","unstructured":"Dillencourt, M.B., Mount, D.M., Saalfeld, A.: On the maximum number of intersections of two polyhedra in 2 and 3 dimensions. In: 5th Canadian Conference on Computational Geometry (Waterloo 1993), pp. 49\u201354. University of Waterloo (1993)"},{"issue":"4","key":"438_CR4","doi-asserted-by":"publisher","first-page":"999","DOI":"10.1007\/s00454-019-00167-x","volume":"65","author":"V Dujmovi\u0107","year":"2021","unstructured":"Dujmovi\u0107, V., Frati, F., Gon\u00e7alves, D., Morin, P., Rote, G.: Every collinear set in a planar graph is free. Discrete Comput. Geom. 65(4), 999\u20131027 (2021)","journal-title":"Discrete Comput. Geom."},{"key":"438_CR5","unstructured":"Erd\u0151s, P., Moser, L.: On the representation of directed graphs as unions of orderings. Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl. 9, 125\u2013132 (1964)"},{"key":"438_CR6","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."},{"issue":"1\u20132","key":"438_CR7","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/S0377-0427(98)00202-7","volume":"101","author":"MS Floater","year":"1999","unstructured":"Floater, M.S., Gotsman, C.: How to morph tilings injectively. J. Comput. Appl. Math. 101(1\u20132), 117\u2013129 (1999)","journal-title":"J. Comput. Appl. Math."},{"key":"438_CR8","unstructured":"G\u00fcnther, F.: The maximum number of intersections of two polygons (2012). arXiv:1207.0996"},{"issue":"1","key":"438_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02574361","volume":"12","author":"J Pach","year":"1994","unstructured":"Pach, J., T\u00f6r\u0151csik, J.: Some geometric applications of Dilworth\u2019s theorem. Discrete Comput. Geom. 12(1), 1\u20137 (1994)","journal-title":"Discrete Comput. Geom."}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00438-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-022-00438-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00438-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,19]],"date-time":"2023-01-19T19:30:13Z","timestamp":1674156613000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-022-00438-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,12]]},"references-count":9,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["438"],"URL":"https:\/\/doi.org\/10.1007\/s00454-022-00438-0","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2022,10,12]]},"assertion":[{"value":"16 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 July 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 July 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 October 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2023","order":5,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":6,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Missing Open Access funding information has been added in the Funding Note.","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}