2026-07-21T19:18:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7183 2024-03-06T10:40:00Z ddc:004 open_access

Computing the Geometric Intersection Number of Curves Despré, Vincent Lazarus, Francis computational topology curves on surfaces combinatorial geodesic 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 c represented by a closed walk of length at most l on a combinatorial surface of complexity n we describe simple algorithms to (1) compute the geometric intersection number of c in O(n+ l^2) time, (2) construct a curve homotopic to c that realizes this geometric intersection number in O(n+l^4) time, (3) decide if the geometric intersection number of c is zero, i.e. if c is homotopic to a simple curve, in O(n+l log^2 l) time. 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 O(n+g^2l^2) time complexity on a genus g surface without boundary. No polynomial time algorithm was known for problem (2). Interestingly, our solution to problem (3) is the first quasi-linear algorithm since the problem was raised by Poincare 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 l in O(n+ l^2) time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vincent Despré and Francis Lazarus 2017 Is Part Of LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2017.35 urn:nbn:de:0030-drops-71838 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.35 eng https://creativecommons.org/licenses/by/3.0/legalcode