{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T22:36:11Z","timestamp":1784673371023,"version":"3.55.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2019,11,25]],"date-time":"2019-11-25T00:00:00Z","timestamp":1574640000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,12,31]]},"abstract":"<jats:p>\n            The geometric intersection number of a curve on a surface is the minimal number of self-intersections of any homotopic curve, i.e., of any curve obtained by continuous deformation. Given a curve\n            <jats:italic>c<\/jats:italic>\n            represented by a closed walk of length at most \u2113 on a combinatorial surface of complexity\n            <jats:italic>n<\/jats:italic>\n            , we describe simple algorithms to (1) compute the geometric intersection number of\n            <jats:italic>c<\/jats:italic>\n            in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            + \u2113\n            <jats:sup>2<\/jats:sup>\n            ) time, (2) construct a curve homotopic to\n            <jats:italic>c<\/jats:italic>\n            that realizes this geometric intersection number in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            +\u2113\n            <jats:sup>4<\/jats:sup>\n            ) time, and (3) decide if the geometric intersection number of\n            <jats:italic>c<\/jats:italic>\n            is zero, i.e., if\n            <jats:italic>c<\/jats:italic>\n            is homotopic to a simple curve, in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            +\u2113 log \u2113) time. The algorithms for (2) and (3) are restricted to orientable surfaces, but the algorithm for (1) is also valid on non-orientable surfaces.\n          <\/jats:p>\n          <jats:p>\n            To our knowledge, no exact complexity analysis had yet appeared on those problems. An optimistic analysis of the complexity of the published algorithms for problems (1) and (3) gives at best a\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>g<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            \u2113\n            <jats:sup>2<\/jats:sup>\n            ) time complexity on a genus\n            <jats:italic>g<\/jats:italic>\n            surface without boundary. No polynomial time algorithm was known for problem (2) for surfaces without boundary. Interestingly, our solution to problem (3) provides a quasi-linear algorithm to a problem raised by Poincar\u00e9 more than a century ago. Finally, we note that our algorithm for problem (1) extends to computing the geometric intersection number of two curves of length at most \u2113 in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            + \u2113\n            <jats:sup>2<\/jats:sup>\n            ) time.\n          <\/jats:p>","DOI":"10.1145\/3363367","type":"journal-article","created":{"date-parts":[[2019,11,26]],"date-time":"2019-11-26T13:08:55Z","timestamp":1574773735000},"page":"1-49","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Computing the Geometric Intersection Number of Curves"],"prefix":"10.1145","volume":"66","author":[{"given":"Vincent","family":"Despr\u00e9","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Nancy, Nancy, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Francis","family":"Lazarus","sequence":"additional","affiliation":[{"name":"CNRS, Grenoble, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,11,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9918-3"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218216515500583"},{"key":"e_1_2_1_3_1","first-page":"592","article-title":"Problem 84-2 (Leo Guibas Editor)","volume":"5","author":"Bentley Jon","year":"1984","unstructured":"Jon Bentley, Charles Leiserson, Ronald Rivest, and Christopher van Wyk. 1984. Problem 84-2 (Leo Guibas Editor). J. Algor. 5, 4 (1984), 592--594.","journal-title":"J. Algor."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-29.2.331"},{"key":"e_1_2_1_5_1","volume-title":"Geometry and Spectra of Compact Riemann Surfaces","author":"Buser Peter","unstructured":"Peter Buser. 1992. Geometry and Spectra of Compact Riemann Surfaces. Birkh\u00e4user."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.8"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.110"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1080\/10586458.2014.897925"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-011-0350-7"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/1.3.310"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/3.1.23"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01431419"},{"key":"e_1_2_1_13_1","volume-title":"Paths of geodesics and geometric intersection numbers: I","author":"Cohen Marshall","unstructured":"Marshall Cohen and Martin Lustig. 1987. Paths of geodesics and geometric intersection numbers: I. In Combinatorial Group Theory and Topology. Ann. of Math. Stud., Vol. 111. Princeton University Press, 479--500."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-1150-2"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1754"},{"key":"e_1_2_1_16_1","volume-title":"th\u00e9orie des groupes et probl\u00e8mes de d\u00e9cision: c\u00e9l\u00e9bration d\u2019un article de Max Dehn de","author":"La Harpe Pierre De","year":"1910","unstructured":"Pierre De La Harpe. 2010. Topologie, th\u00e9orie des groupes et probl\u00e8mes de d\u00e9cision: c\u00e9l\u00e9bration d\u2019un article de Max Dehn de 1910. Gazette des math\u00e9maticiens 125 (2010), 41--75."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1619"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.118"},{"key":"e_1_2_1_19_1","volume-title":"A Primer on Mapping Class Groups","author":"Farb Benson","unstructured":"Benson Farb and Dan Margalit. 2012. A Primer on Mapping Class Groups. Princeton University Press."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01233430"},{"key":"e_1_2_1_21_1","first-page":"139","article-title":"An algorithm for minimal number of (self-)intersection points of curves on surfaces","volume":"26","author":"Gon\u00e7alves Daciberg L.","year":"2005","unstructured":"Daciberg L. Gon\u00e7alves, Elena Kudryavtseva, and Heiner Zieschang. 2005. An algorithm for minimal number of (self-)intersection points of curves on surfaces. In Proceedings of the Seminar on Vector and Tensor Analysis, Vol. 26. 139--167.","journal-title":"Proceedings of the Seminar on Vector and Tensor Analysis"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02772960"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0040-9383(94)90033-7"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.2140\/gtm.1999.2.201"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.12"},{"key":"e_1_2_1_27_1","volume-title":"Combinatorics on Words","author":"Lothaire M.","unstructured":"M. Lothaire. 1997. Combinatorics on Words. Cambridge University Press."},{"key":"e_1_2_1_28_1","volume-title":"Paths of geodesics and geometric intersection numbers: II","author":"Lustig Martin","unstructured":"Martin Lustig. 1987. Paths of geodesics and geometric intersection numbers: II. In Combinatorial Group Theory and Topology. Ann. of Math. Stud., Vol. 111. Princeton University Press, 501--543."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Maryam Mirzakhani. 2008. Growth of the number of simple closed geodesics on hyperbolic surfaces. Ann. Math. (2008) 97--125.","DOI":"10.4007\/annals.2008.168.97"},{"key":"e_1_2_1_30_1","unstructured":"Maryam Mirzakhani. 2016. Counting Mapping Class group orbits on hyperbolic surfaces. Preprint arxiv:1601.03342."},{"key":"e_1_2_1_31_1","volume-title":"Graphs on Surfaces","author":"Mohar Bojan","unstructured":"Bojan Mohar and Carsten Thomassen. 2001. Graphs on Surfaces. Johns Hopkins University Press."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.2140\/agt.2001.1.349"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-8641(01)00202-4"},{"key":"e_1_2_1_34_1","volume-title":"Cinqui\u00e8me compl\u00e9ment \u00e0 l\u2019analysis situs. Rendiconti del Circolo Matematico di Palermo 18, 1","author":"Poincar\u00e9 Henri","year":"1904","unstructured":"Henri Poincar\u00e9. 1904. Cinqui\u00e8me compl\u00e9ment \u00e0 l\u2019analysis situs. Rendiconti del Circolo Matematico di Palermo 18, 1 (1904), 45--110."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.2307\/1970169"},{"key":"e_1_2_1_36_1","unstructured":"Jenya Sapir. 2015. Bounds on the number of non-simple closed geodesics on a surface. Preprint arxiv:1505.07171."},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the Canadian Conference on Computational Geometry (CCCG\u201908)","author":"Schaefer Marcus","year":"2008","unstructured":"Marcus Schaefer, Eric Sedgwick, and Daniel Stefankovic. 2008. Computing Dehn twists and geometric intersection numbers in polynomial time. In Proceedings of the Canadian Conference on Computational Geometry (CCCG\u201908). 111--114."},{"key":"e_1_2_1_38_1","volume-title":"Classical Topology and Combinatorial Group Theory","author":"Stillwell J.","unstructured":"J. Stillwell. 1993. Classical Topology and Combinatorial Group Theory. Springer."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1070\/SM1979v035n02ABEH001471"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-10761"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-10940"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3363367","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3363367","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:12:52Z","timestamp":1750201972000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3363367"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,25]]},"references-count":41,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3363367"],"URL":"https:\/\/doi.org\/10.1145\/3363367","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,25]]},"assertion":[{"value":"2017-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-11-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}