Tightening curves on surfaces via local moves

Hsien Chih Chang, Jeff Erickson, David Letscher, Arnaud De Mesmay, Saul Schleimer, Eric Sedgwick, Dylan Thurston, Stephan Tillmann

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

Abstract

We prove new upper and lower bounds on the number of homotopy moves required to tighten a closed curve on a compact orientable surface (with or without boundary) as much as possible. First, we prove that (n2) moves are required in the worst case to tighten a contractible closed curve on a surface with non-positive Euler characteristic, where n is the number of self-intersection points. Results of Hass and Scott imply a matching O(n2) upper bound for contractible curves on orientable surfaces. Second, we prove that any closed curve on any orientable surface can be tightened as much as possible using at most O(n4) homotopy moves. Except for a few special cases, only naïve exponential upper bounds were previously known for this problem.

Original languageEnglish (US)
Title of host publication29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
EditorsArtur Czumaj
PublisherAssociation for Computing Machinery
Pages121-135
Number of pages15
ISBN (Electronic)9781611975031
DOIs
StatePublished - 2018
Event29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 - New Orleans, United States
Duration: Jan 7 2018Jan 10 2018

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
CountryUnited States
CityNew Orleans
Period1/7/181/10/18

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Tightening curves on surfaces via local moves'. Together they form a unique fingerprint.

Cite this