Document Open Access Logo

Computing the Geometric Intersection Number of Curves

Authors Vincent Despré, Francis Lazarus

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.35.pdf
  • Filesize: 0.64 MB
  • 15 pages

Document Identifiers

Author Details

Vincent Despré
Francis Lazarus

Cite As Get BibTex

Vincent Despré and Francis Lazarus. Computing the Geometric Intersection Number of Curves. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SoCG.2017.35

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 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 quasi-linear 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.

Subject Classification

Keywords
  • computational topology
  • curves on surfaces
  • combinatorial geodesic

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Chris Arettines. A combinatorial algorithm for visualizing representatives with minimal self-intersection. J. Knot Theor. Ramif., 24(11):1-17, 2015. Google Scholar
  2. Joan S. Birman and Caroline Series. An algorithm for simple curves on surfaces. J. London Math. Soc., 29(2):331-342, 1984. Google Scholar
  3. Hsien-Chih Chang and Jeff Erickson. Untangling planar curves. In Proc. 32nd Int'l Symp. Comput. Geom. (SoCG), volume 51, pages 29:1-15, 2016. Google Scholar
  4. Hsien-Chih Chang, Jeff Erickson, and Chao Xu. Detecting weakly simple polygons. In Proc. 26th ACM-SIAM Symp. Discrete Alg. (SODA), pages 1655-1670, 2015. Google Scholar
  5. Moira Chas. Self-intersection numbers of length-equivalent curves on surfaces. Exp. Math., 23(3):271-276, 2014. Google Scholar
  6. Moira Chas and Steven P. Lalley. Self-intersections in combinatorial topology: statistical structure. Invent. Math., 188(2):429-463, 2012. Google Scholar
  7. David R. J. Chillingworth. Simple closed curves on surfaces. Bull. London Math. Soc., 1(3):310-314, 1969. Google Scholar
  8. David R. J. Chillingworth. Winding numbers on surfaces. II. Math. Ann., 199(3):131-153, 1972. Google Scholar
  9. Marshall Cohen and Martin Lustig. Paths of geodesics and geometric intersection numbers: I. In Combinatorial group theory and topology, volume 111 of Ann. Math. Stud., pages 479-500. Princeton Univ. Press, 1987. Google Scholar
  10. Éric Colin de Verdière and Francis Lazarus. Optimal System of Loops on an Orientable Surface. Discrete Comput. Geom., 33(3):507-534, 2005. Google Scholar
  11. Maurits de Graaf and Alexander Schrijver. Making curves minimally crossing by Reidemeister moves. J. Com. Theory B, 70(1):134-156, 1997. Google Scholar
  12. Pierre De La Harpe. Topologie, théorie des groupes et problèmes de décision: célébration d'un article de max dehn de 1910. Gazette des mathématiciens, 125:41-75, 2010. Google Scholar
  13. Tamal K. Dey and Sumanta Guha. Transforming Curves on Surfaces. J. Comput. and Syst. Sci., 58(2):297-325, 1999. Google Scholar
  14. David Epstein and Derek Holt. The linearity of the conjugacy problem in word-hyperbolic groups. Int'l J. Algebr. Comput., 16(02):287-305, 2006. Google Scholar
  15. Jeff Erickson and Kim Whittelsey. Transforming curves on surfaces redux. In Proc. 24th ACM-SIAM Symp. Discrete Alg. (SODA), 2013. Google Scholar
  16. Benson Farb and Dan Margalit. A primer on mapping class groups. Princeton Univ. Press, 2012. Google Scholar
  17. Steve M. Gersten and Hamish B. Short. Small cancellation theory and automatic groups. Invent. Math., 102:305-334, 1990. Google Scholar
  18. Daciberg L. Gonçalves, Elena Kudryavtseva, and Heiner Zieschang. An algorithm for minimal number of (self-)intersection points of curves on surfaces. In Proc. Seminar on Vector and Tensor Analysis, volume 26, pages 139-167, 2005. Google Scholar
  19. Joel Hass and Peter Scott. Intersections of curves on surfaces. Isr. J. Math., 51(1-2):90-120, 1985. Google Scholar
  20. Joel Hass and Peter Scott. Configurations of curves and geodesics on surfaces. Geometry and Topology Monographs, 2:201-213, 1999. Google Scholar
  21. Donald E. Knuth, James H. Morris, Jr, and Vaughan R. Pratt. Fast pattern matching in strings. SIAM J. Comput., 6(2):323-350, 1977. Google Scholar
  22. Francis Lazarus and Julien Rivaud. On the homotopy test on surfaces. In Proc. 53rd IEEE Symp. Found. Comput. Sci. (FOCS), pages 440-449, 2012. Google Scholar
  23. Martin Lustig. Paths of geodesics and geometric intersection numbers: II. In Combinatorial group theory and topology, volume 111 of Ann. of Math. Stud., pages 501-543. Princeton Univ. Press, 1987. Google Scholar
  24. Maryam Mirzakhani. Growth of the number of simple closed geodesies on hyperbolic surfaces. Ann. Math., pages 97-125, 2008. Google Scholar
  25. Maryam Mirzakhani. Counting mapping class group orbits on hyperbolic surfaces. Preprint http://arxiv.org/pdf/1601.03342, January 2016.
  26. Bojan Mohar and Carsten Thomassen. Graphs on Surfaces. Studies in the Mathematical Sciences. Johns Hopkins Univ. Press, 2001. Google Scholar
  27. Max Neumann-Coto. A characterization of shortest geodesics on surfaces. Algebr. Geom. Topol., 1:349-368, 2001. Google Scholar
  28. J. M. Paterson. A combinatorial algorithm for immersed loops in surfaces. Topol. Appl., 123(2):205-234, 2002. Google Scholar
  29. Henri Poincaré. Cinquième complément à l'analysis situs. Rendiconti del Circolo Matematico di Palermo, 18(1):45-110, 1904. Google Scholar
  30. Bruce L. Reinhart. Algorithms for Jordan curves on compact surfaces. Ann. Math., pages 209-222, 1962. Google Scholar
  31. Jenya Sapir. Bounds on the number of non-simple closed geodesics on a surface. Preprint http://arxiv.org/pdf/1505.07171, May 2015. URL: http://arxiv.org/abs/1505.07171.
  32. Marcus Schaefer, Eric Sedgwick, and Daniel Stefankovic. Computing Dehn twists and geometric intersection numbers in polynomial time. In CCCG, pages 111-114, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact