Search Results

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].