Transforming curves on surfaces redux

Jeff Erickson, Kim Whittlesey

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Almost exactly 100 years ago, Max Dehn described the first combinatorial algorithm to determine whether two given cycles on a compact surface are homotopic, meaning one cycle can be continuously deformed into the other without leaving the surface. We describe a simple variant of Dehn's algorithm that runs in linear time, with no hidden dependence on the genus of the surface. Specifically, given two closed vertex-edge walks of length at most ℓ in a combinatorial surface of complexity n, our algorithm determines whether the walks are homotopic in O(n + ℓ) time. Our algorithm simplifies and corrects a similar algorithm of Dey and Guha [JCSS 1999] and simplifies the more recent algorithm of Lazarus and Rivaud [FOCS 2012], who identified a subtle flaw in Dey and Guha's results. Our algorithm combines components of these earlier algorithms, classical results in small cancellation theory by Gersten and Short [Inventiones 1990], and simple run-length encoding.

Original languageEnglish (US)
Title of host publicationProceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
PublisherAssociation for Computing Machinery
Pages1646-1655
Number of pages10
ISBN (Print)9781611972511
DOIs
StatePublished - 2013
Event24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 - New Orleans, LA, United States
Duration: Jan 6 2013Jan 8 2013

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
CountryUnited States
CityNew Orleans, LA
Period1/6/131/8/13

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Transforming curves on surfaces redux'. Together they form a unique fingerprint.

  • Cite this

    Erickson, J., & Whittlesey, K. (2013). Transforming curves on surfaces redux. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 (pp. 1646-1655). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery. https://doi.org/10.1137/1.9781611973105.118