Despré, Vincent ;
Lazarus, Francis
Computing the Geometric Intersection Number of Curves
Abstract
The geometric intersection number of a curve on a surface is the minimal number of selfintersections 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 quasilinear 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.
BibTeX  Entry
@InProceedings{despr_et_al:LIPIcs:2017:7183,
author = {Vincent Despr{\'e} and Francis Lazarus},
title = {{Computing the Geometric Intersection Number of Curves}},
booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)},
pages = {35:135:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770385},
ISSN = {18688969},
year = {2017},
volume = {77},
editor = {Boris Aronov and Matthew J. Katz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7183},
URN = {urn:nbn:de:0030drops71838},
doi = {10.4230/LIPIcs.SoCG.2017.35},
annote = {Keywords: computational topology, curves on surfaces, combinatorial geodesic}
}
2017
Keywords: 

computational topology, curves on surfaces, combinatorial geodesic 
Seminar: 

33rd International Symposium on Computational Geometry (SoCG 2017)

Issue date: 

2017 
Date of publication: 

2017 