TY - GEN

T1 - Tightening curves on surfaces via local moves

AU - Chang, Hsien Chih

AU - Erickson, Jeff

AU - Letscher, David

AU - De Mesmay, Arnaud

AU - Schleimer, Saul

AU - Sedgwick, Eric

AU - Thurston, Dylan

AU - Tillmann, Stephan

N1 - Funding Information:
∗Department of Computer Science, University of Illinois at Urbana-Champaign, USA. Work by these authors was partially supported by NSF grant CCF-1408763. †Department of Computer Science, Saint Louis University, USA. Work by this author was partially supported by NSF grant IIS-1319944. ‡Univ. Grenoble Alpes, CNRS, Grenoble INP, GIPSA-lab, 38000 Grenoble, France. Work by this author was partially supported by the French project ANR-16-CE40-0009-01 (GATO). §Warwick Mathematics Institute, University of Warwick, Coventry, UK. ¶School of Computing, DePaul University, Chicago, USA. ‖Department of Mathematics, Indiana University, Bloomington, USA. ∗∗School of Mathematics and Statistics, The University of Sydney, Australia. Work by this author was partially supported under the Australian Research Council’s Discovery funding scheme (project number DP160104502).

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85045548809&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85045548809&partnerID=8YFLogxK

U2 - 10.1137/1.9781611975031.8

DO - 10.1137/1.9781611975031.8

M3 - Conference contribution

AN - SCOPUS:85045548809

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 121

EP - 135

BT - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

A2 - Czumaj, Artur

PB - Association for Computing Machinery

T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

Y2 - 7 January 2018 through 10 January 2018

ER -