preprint · HAL (Le Centre pour la Communication Scientifique Directe) · 2015

Computing the Geometric Intersection Number of Curves

Cited by 5Open access

Abstract

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 $\ell$ on a combinatorial surface of complexity $n$ we describe simple algorithms to (1) compute the geometric intersection number of $c$ in $O(n+ \ell^2)$ time, (2) construct a curve homotopic to $c$ that realizes this geometric intersection number in $O(n+\ell^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+\ell\log\ell)$ time. The algorithms for (2) and (3) are restricted to orientable surfaces, but the algorithm for (1) is also valid on non-orientable surfaces. 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^2\ell^2)$ time complexity on a genus $g$ 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é 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 $\ell$ in $O(n+ \ell^2)$ time.

Cite this paper

APA 7

Despré, V., & Lazarus, F. (2015). Computing the Geometric Intersection Number of Curves. HAL (Le Centre pour la Communication Scientifique Directe). https://doi.org/10.48550/arxiv.1511.09327

MLA 9

Despré, Vincent, and Francis Lazarus. “Computing the Geometric Intersection Number of Curves.” HAL (Le Centre pour la Communication Scientifique Directe), 2015, https://doi.org/10.48550/arxiv.1511.09327.

Chicago

Despré, Vincent, and Francis Lazarus. 2015. “Computing the Geometric Intersection Number of Curves.” HAL (Le Centre pour la Communication Scientifique Directe). https://doi.org/10.48550/arxiv.1511.09327.

Harvard

Despré, V. and Lazarus, F. (2015) ‘Computing the Geometric Intersection Number of Curves’, HAL (Le Centre pour la Communication Scientifique Directe). Available at: https://doi.org/10.48550/arxiv.1511.09327.

BibTeX

@misc{despre2015computing,
  title = {{Computing the Geometric Intersection Number of Curves}},
  author = {Despré, Vincent and Lazarus, Francis},
  journal = {HAL (Le Centre pour la Communication Scientifique Directe)},
  year = {2015},
  doi = {10.48550/arxiv.1511.09327}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.