2026-08-06T07:55:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21121 2024-09-23T09:13:17Z ddc:004 open_access

Making Multicurves Cross Minimally on Surfaces Dubois, Loïc Algorithms Topology Surfaces Closed Curves Geometric Intersection Number On an orientable surface S, consider a collection Γ of closed curves. The (geometric) intersection number i_S(Γ) is the minimum number of self-intersections that a collection Γ' can have, where Γ' results from a continuous deformation (homotopy) of Γ. We provide algorithms that compute i_S(Γ) and such a Γ', assuming that Γ is given by a collection of closed walks of length n in a graph M cellularly embedded on S, in O(n log n) time when M and S are fixed. The state of the art is a paper of Despré and Lazarus [SoCG 2017, J. ACM 2019], who compute i_S(Γ) in O(n²) time, and Γ' in O(n⁴) time if Γ is a single closed curve. Our result is more general since we can put an arbitrary number of closed curves in minimal position. Also, our algorithms are quasi-linear in n instead of quadratic and quartic. Most importantly, our proofs are simpler, shorter, and more structured. We use techniques from two-dimensional topology and from the theory of hyperbolic surfaces. Most notably, we prove a new property of the reducing triangulations introduced by Colin de Verdière, Despré, and Dubois [SODA 2024], reducing our problem to the case of surfaces with boundary. As a key subroutine, we rely on an algorithm of Fulek and Tóth [JCO 2020]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Loïc Dubois 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.50 urn:nbn:de:0030-drops-211216 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.50 eng https://creativecommons.org/licenses/by/4.0/legalcode