Tightening Curves on Surfaces via Local Moves
| Autor: | Saul Schleimer, Eric Sedgwick, Stephan Tillmann, David Letscher, Dylan P. Thurston, Hsien-Chih Chang, Arnaud de Mesmay, Jeff Erickson |
|---|---|
| Přispěvatelé: | University of Illinois at Urbana-Champaign [Urbana], University of Illinois System, Saint Louis University, GIPSA - Architecture, Géométrie, Perception, Images, Gestes (GIPSA-AGPIG), Département Images et Signal (GIPSA-DIS), Grenoble Images Parole Signal Automatique (GIPSA-lab ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Grenoble Images Parole Signal Automatique (GIPSA-lab ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Centre National de la Recherche Scientifique (CNRS), Warwick Mathematics Institute (WMI), University of Warwick [Coventry], School of Computing [DePaul] (SOC), DePaul University [Chicago], Indiana University [Bloomington], Indiana University System, The University of Sydney |
| Rok vydání: | 2018 |
| Předmět: |
Surface (mathematics)
Pure mathematics Matching (graph theory) Homotopy 010102 general mathematics Boundary (topology) 0102 computer and information sciences [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] 01 natural sciences Upper and lower bounds Contractible space Exponential function symbols.namesake 010201 computation theory & mathematics [MATH.MATH-GT]Mathematics [math]/Geometric Topology [math.GT] Euler characteristic symbols 0101 mathematics ComputingMilieux_MISCELLANEOUS Mathematics |
| Zdroj: | SODA ACM-SIAM Symposium on Discrete Algorithms ACM-SIAM Symposium on Discrete Algorithms, Jan 2018, New Orleans, United States |
| DOI: | 10.1137/1.9781611975031.8 |
| Popis: | 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 0(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 0(n4) homotopy moves. Except for a few special cases, only naive exponential upper bounds were previously known for this problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|