Chang, Hsien-Chih, Erickson, Jeff, Letscher, David, de Mesmay, Arnaud, Schleimer, Saul, Sedgwick, Eric, Thurston, Dylan and Tillmann, Stephan (2017) Tightening curves on surfaces via local moves. In: ACM-SIAM Symposium on Discrete Algorithms, New Orleans, USA, 7-10 Jan 2018. Published in: SODA 18 : Proceedings of ACM-SIAM Symposium on Discrete Algorithms

Preview

PDF WRAP-tightening-curves-surfaces-local-moves-Schleimer-2017.pdf - Accepted Version - Requires a PDF viewer. Download (1369Kb) | Preview

Request Changes to record.

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 Ω(n²) 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(n²) 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(n⁴) homotopy moves. Except for a few special cases, only naïve exponential upper bounds were previously known for this problem.

Item Type:	Conference Item (Paper)
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science, Engineering and Medicine > Science > Mathematics
Library of Congress Subject Headings (LCSH):	Homotopy theory, Topology
Journal or Publication Title:	SODA 18 : Proceedings of ACM-SIAM Symposium on Discrete Algorithms
Publisher:	Society for Industrial and Applied Mathematics
Official Date:	1 November 2017
Dates:	Date Event 1 November 2017 Accepted
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Date of first compliant deposit:	3 November 2017
Date of first compliant Open Access:	6 November 2017
Conference Paper Type:	Paper
Title of Event:	ACM-SIAM Symposium on Discrete Algorithms
Type of Event:	Conference
Location of Event:	New Orleans, USA
Date(s) of Event:	7-10 Jan 2018
Related URLs:	Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads