Vincent Despré
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 ℓ on a combinatorial surface of complexity n, we describe simple algorithms to (1) compute the geometric intersection number of c in O(n+ ℓ2) time, (2) construct a curve homotopic to c that realizes this geometric intersection number in O(n+ℓ4) time, and (3) decide if the geometric intersection number of c is zero, i.e., if c is homotopic to a simple curve, in O(n+ℓ log ℓ) 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+g2ℓ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 ℓ in O(n+ ℓ2) time.
- Hugo A. Akitaya, Greg Aloupis, Jeff Erickson, and Csaba D. Tóth. 2017. Recognizing weakly simple polygons. Discrete Comput. Geom. 58, 4 (2017), 785--821. http://jeffe.cs.illinois.edu/pubs/fastweak.html.Google Scholar
Digital Library
- Chris Arettines. 2015. A combinatorial algorithm for visualizing representatives with minimal self-intersection. J. Knot Theory Ramificat. 24, 11 (2015), 1--17.Google ScholarCross Ref
- Jon Bentley, Charles Leiserson, Ronald Rivest, and Christopher van Wyk. 1984. Problem 84-2 (Leo Guibas Editor). J. Algor. 5, 4 (1984), 592--594.Google Scholar
- Joan S. Birman and Caroline Series. 1984. An algorithm for simple curves on surfaces. J. London Math. Soc. 29, 2 (1984), 331--342.Google ScholarCross Ref
- Peter Buser. 1992. Geometry and Spectra of Compact Riemann Surfaces. Birkhäuser.Google Scholar
- Hsien-Chih Chang, Jeff Erickson, David Letscher, Arnaud De Mesmay, Saul Schleimer, Eric Sedgwick, Dylan Thurston, and Stephan Tillmann. 2018. Tightening curves on surfaces via local moves. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 121--135.Google ScholarCross Ref
- Hsien-Chih Chang, Jeff Erickson, and Chao Xu. 2015. Detecting weakly simple polygons. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms. 1655--1670.Google ScholarCross Ref
- Moira Chas. 2014. Self-intersection numbers of length-equivalent curves on surfaces. Exper. Math. 23, 3 (2014), 271--276.Google ScholarCross Ref
- Moira Chas and Steven P. Lalley. 2012. Self-intersections in combinatorial topology: Statistical structure. Invent. Math. 188, 2 (2012), 429--463.Google ScholarCross Ref
- David R. J. Chillingworth. 1969. Simple closed curves on surfaces. Bull. London Math. Soc. 1, 3 (1969), 310--314.Google ScholarCross Ref
- David R. J. Chillingworth. 1971. An algorithm for families of disjoint simple closed curves on surfaces. Bull. London Math. Soc. 3, 1 (1971), 23--26.Google ScholarCross Ref
- David R. J. Chillingworth. 1972. Winding numbers on surfaces. II. Math. Ann. 199, 3 (1972), 131--153.Google ScholarCross Ref
- Marshall Cohen and Martin Lustig. 1987. Paths of geodesics and geometric intersection numbers: I. In Combinatorial Group Theory and Topology. Ann. of Math. Stud., Vol. 111. Princeton University Press, 479--500.Google Scholar
- Éric Colin de Verdière and Francis Lazarus. 2005. Optimal system of loops on an orientable surface. Discrete Comput. Geom. 33, 3 (Mar. 2005), 507--534.Google ScholarDigital Library
- Maurits de Graaf and Alexander Schrijver. 1997. Making curves minimally crossing by Reidemeister moves. J. Combinator. Theory, Ser. B 70, 1 (1997), 134--156.Google ScholarDigital Library
- Pierre De La Harpe. 2010. 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 (2010), 41--75.Google Scholar
- Tamal K. Dey and Sumanta Guha. 1999. Transforming curves on surfaces. J. Comput. Syst. Sci. 58, 2 (1999), 297--325.Google ScholarDigital Library
- Jeff Erickson and Kim Whittelsey. 2013. Transforming curves on surfaces redux. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms.Google ScholarCross Ref
- Benson Farb and Dan Margalit. 2012. A Primer on Mapping Class Groups. Princeton University Press.Google Scholar
- Steve M. Gersten and Hamish B. Short. 1990. Small cancellation theory and automatic groups. Invent. Math. 102 (1990), 305--334.Google ScholarCross Ref
- Daciberg L. Gonçalves, Elena Kudryavtseva, and Heiner Zieschang. 2005. An algorithm for minimal number of (self-)intersection points of curves on surfaces. In Proceedings of the Seminar on Vector and Tensor Analysis, Vol. 26. 139--167.Google Scholar
- Joel Hass and Peter Scott. 1985. Intersections of curves on surfaces. Israel. Math. 51, 1--2 (1985), 90--120.Google ScholarCross Ref
- Joel Hass and Peter Scott. 1994. Shortening curves on surfaces. Topology 33, 1 (1994), 25--43.Google ScholarCross Ref
- Joel Hass and Peter Scott. 1999. Configurations of curves and geodesics on surfaces. Geom. Topol. Monogr. 2 (1999), 201--213.Google ScholarCross Ref
- Donald E. Knuth, James H. Morris, Jr., and Vaughan R. Pratt. 1977. Fast pattern matching in strings. SIAM J. Comput. 6, 2 (1977), 323--350.Google ScholarDigital Library
- Francis Lazarus and Julien Rivaud. 2012. On the homotopy test on surfaces. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science. 440--449.Google ScholarDigital Library
- M. Lothaire. 1997. Combinatorics on Words. Cambridge University Press.Google Scholar
- Martin Lustig. 1987. Paths of geodesics and geometric intersection numbers: II. In Combinatorial Group Theory and Topology. Ann. of Math. Stud., Vol. 111. Princeton University Press, 501--543.Google Scholar
- Maryam Mirzakhani. 2008. Growth of the number of simple closed geodesics on hyperbolic surfaces. Ann. Math. (2008), 97--125.Google Scholar
- Maryam Mirzakhani. 2016. Counting Mapping Class group orbits on hyperbolic surfaces. Preprint arxiv:1601.03342.Google Scholar
- Bojan Mohar and Carsten Thomassen. 2001. Graphs on Surfaces. Johns Hopkins University Press.Google Scholar
- Max Neumann-Coto. 2001. A characterization of shortest geodesics on surfaces. Alg. Geom. Topol. 1 (2001), 349--368.Google ScholarCross Ref
- J. M. Paterson. 2002. A combinatorial algorithm for immersed loops in surfaces. Topol. Appl. 123, 2 (2002), 205--234.Google ScholarCross Ref
- Henri Poincaré. 1904. Cinquième complément à l’analysis situs. Rendiconti del Circolo Matematico di Palermo 18, 1 (1904), 45--110.Google Scholar
- Bruce L. Reinhart. 1962. Algorithms for Jordan curves on compact surfaces. Ann. Math. 75, 2 (1962), 209--222.Google ScholarCross Ref
- Jenya Sapir. 2015. Bounds on the number of non-simple closed geodesics on a surface. Preprint arxiv:1505.07171.Google Scholar
- Marcus Schaefer, Eric Sedgwick, and Daniel Stefankovic. 2008. Computing Dehn twists and geometric intersection numbers in polynomial time. In Proceedings of the Canadian Conference on Computational Geometry (CCCG’08). 111--114.Google Scholar
- J. Stillwell. 1993. Classical Topology and Combinatorial Group Theory. Springer.Google Scholar
- Vladimir G. Turaev. 1979. Intersections of loops in two-dimensional manifolds. Math. USSR-Sbornik 35, 2 (1979), 229.Google ScholarCross Ref
- Heiner Zieschang. 1965. Algorithmen für einfache Kurven auf Flächen. Math. Scand. 17 (1965), 17--40.Google ScholarCross Ref
- Heiner Zieschang. 1969. Algorithmen für einfache Kurven auf Flächen II. Math. Scand. 25 (1969), 49--58.Google ScholarCross Ref
Index Terms
- Computing the Geometric Intersection Number of Curves
Recommendations
G1 continuous approximate curves on NURBS surfaces
Curves on surfaces play an important role in computer aided geometric design. In this paper, we present a parabola approximation method based on the cubic reparameterization of rational Bézier surfaces, which generates G1 continuous approximate curves ...
Projection of curves on B-spline surfaces using quadratic reparameterization
Curves on surfaces play an important role in computer aided geometric design. In this paper, we present a hyperbola approximation method based on the quadratic reparameterization of Bezier surfaces, which generates reasonable low degree curves lying ...
Approximate computation of curves on B-spline surfaces
Curves on surfaces play an important role in computer-aided geometric design. Because of the considerably high degree of exact curves on surfaces, approximation algorithms are preferred in CAD systems. To approximate the exact curve with a reasonably ...
Reviews
Joseph J. O'Rourke
More than a century ago, Poincaré asked for a procedure to determine if a closed curve on a compact surface S could be contracted to a point, and suggested a computationally expensive method. Dehn proposed a simpler combinatorial algorithm, which, optimistically, depends heavily on the genus g of the surface S . A central achievement of the Despré and Lazarus paper is an efficient algorithm for answering Poincaré's question. This 49-page paper contains several results, but this review concentrates on just detecting whether has geometric intersection number zero, equivalent to contractibility. It is assumed the surface S is given as a polygonal decomposition of total complexity n , and that is given as a walk on the 1-skeleton of steps. Their result is an algorithm with time complexity O ( n + log ), independent of g . Their work builds on that of a collection of papers over the last 50 years, which show that a series of reductions turns the problem into a purely combinatorial question. The surface is given a hyperbolic metric, which leads a unique geodesic in its "homotopic class," its equivalence class under deformations. The surface polygonization can be reduced to a system of quadrilaterals in linear time, and a canonical form for can be constructed in linear time, which can be further reduced to a "homotopic geodesic," again in linear time. Finally, this reduced is untangled by the authors' "unzipping" algorithm, which results in a simple (zero-intersection) representation exactly when is contractible. The proof of this is a dozen pages of delicate analysis, switching curve crossings on staircases of quadrilaterals. Dehn's algorithm is now superseded after 100 years.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments