Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Computing the geometric intersection number of curves
Despré V., Lazarus F. Journal of the ACM66 (6):1-49,2019.Type:Article
Date Reviewed: Jan 1 2021

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.

Reviewer:  Joseph O’Rourke Review #: CR147151 (2105-0120)
Bookmark and Share
  Featured Reviewer  
 
General (G.0 )
 
 
Combinatorial Algorithms (G.2.1 ... )
 
 
Combinatorics (G.2.1 )
 
 
Graph Theory (G.2.2 )
 
Would you recommend this review?
yes
no
Other reviews under "General": Date

Type: Journal
Feb 1 1986
Science, computers, and people: from the tree of mathematics
Ulam S., Birkhäuser Boston Inc., Cambridge, MA, 1986. Type: Book (9789780817632762)
May 1 1988
Computer science: a mathematical introduction
Lew A., Prentice-Hall, Inc., Upper Saddle River, NJ, 1985. Type: Book (9789780131642522)
Jul 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy