Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2402.04789 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- 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^2)$ time, and $Γ'$ in $O(n^4)$ 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, and our proofs are simpler and shorter. 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].