An official website of the United States government
Blank, in his Ph.D. thesis on determining whether a planar closed curve $$\gamma$$ is self-overlapping, constructed a combinatorial word geometrically over the faces of $$\gamma$$ by drawing cuts from each face to a point at infinity and tracing their intersection points with $$\gamma$$. Independently, Nie, in an unpublished manuscript, gave an algorithm to determine the minimum area swept out by any homotopy from a closed curve $$\gamma$$ to a point. Nie constructed a combinatorial word algebraically over the faces of $$\gamma$$ inspired by ideas from geometric group theory, followed by dynamic programming over the subwords. In this paper, we examine the definitions of the two words and prove the equivalence between Blank's word and Nie's word under the right assumptions.
more »
« less
From Curves to Words and Back Again: Geometric Computation of Minimum-Area Homotopy
Let γ be a generic closed curve in the plane. Samuel Blank, in his 1967 Ph.D. thesis, determined if γ is self-overlapping by geometrically constructing a combinatorial word from γ. More recently, Zipei Nie, in an unpublished manuscript, computed the minimum homotopy area of γ by constructing a combinatorial word algebraically. We provide a unified framework for working with both words and determine the settings under which Blank’s word and Nie’s word are equivalent. Using this equivalence, we give a new geometric proof for the correctness of Nie’s algorithm. Unlike previous work, our proof is constructive which allows us to naturally compute the actual homotopy that realizes the minimum area. Furthermore, we contribute to the theory of self-overlapping curves by providing the first polynomial-time algorithm to compute a self-overlapping decomposition of any closed curve γ with minimum area.
more »
« less
- PAR ID:
- 10509061
- Editor(s):
- Morin, Pat; Suri, Subhash
- Publisher / Repository:
- Springer-Verlag
- Date Published:
- Journal Name:
- Proceedings Algorithms and Data Structures: 18th International Symposium, WADS
- Page Range / eLocation ID:
- 605-619
- Format(s):
- Medium: X
- Location:
- Montreal, QC, Canada
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
In this paper we prove that the problem of deciding contractibility of an arbitrary closed curve on the boundary of a 3-manifold is in NP. We emphasize that the manifold and the curve are both inputs to the problem. Moreover, our algorithm also works if the curve is given as a compressed word. Previously, such an algorithm was known for simple (non-compressed) curves, and, in very limited cases, for curves with self-intersections. Furthermore, our algorithm is fixed-parameter tractable in the size of the input 3-manifold. As part of our proof, we obtain new polynomial-time algorithms for compressed curves on surfaces, which we believe are of independent interest. We provide a polynomial-time algorithm which, given an orientable surface and a compressed loop on the surface, computes a canonical form for the loop as a compressed word. In particular, contractibility of compressed curves on surfaces can be decided in polynomial time; prior published work considered only constant genus surfaces. More generally, we solve the following normal subgroup membership problem in polynomial time: given an arbitrary orientable surface, a compressed closed curve, and a collection of disjoint normal curves, there is a polynomial-time algorithm to decide if the curve lies in the normal subgroup generated by components of the normal curves in the fundamental group of the surface after attaching the curves to a basepoint.more » « less
-
null (Ed.)We give an explicit combinatorial formula for the Laurent expansion of any arc or closed curve on an unpunctured triangulated orbifold. We do this by extending the snake graph construction of Musiker, Schiffler, and Williams to unpunctured orbifolds. In the case of an ordinary arc, this gives a combinatorial proof of positivity to the generalized cluster algebra from this orbifold.more » « less
-
Given a loop or more generally 1-cycle r r of size L on a closed two-dimensional manifold or surface, represented by a triangulated mesh, a question in computational topology asks whether or not it is homologous to zero. We frame and tackle this problem in the quantum setting. Given an oracle that one can use to query the inclusion of edges on a closed curve, we design a quantum algorithm for such a homology detection with a constant running time, with respect to the size or the number of edges on the loop r r , requiring only a single usage of oracle. In contrast, classical algorithm requires \Omega(L) Ω ( L ) oracle usage, followed by a linear time processing and can be improved to logarithmic by using a parallel algorithm. Our quantum algorithm can be extended to check whether two closed loops belong to the same homology class. Furthermore, it can be applied to a specific problem in the homotopy detection, namely, checking whether two curves are not homotopically equivalent on a closed two-dimensional manifold.more » « less
-
Abstract Let $$\Omega $$ be a connected open set in the plane and $$\gamma : [0,1] \to \overline {\Omega }$$ a path such that $$\gamma ((0,1)) \subset \Omega $$ . We show that the path $$\gamma $$ can be “pulled tight” to a unique shortest path which is homotopic to $$\gamma $$ , via a homotopy h with endpoints fixed whose intermediate paths $$h_t$$ , for $$t \in [0,1)$$ , satisfy $$h_t((0,1)) \subset \Omega $$ . We prove this result even in the case when there is no path of finite Euclidean length homotopic to $$\gamma $$ under such a homotopy. For this purpose, we offer three other natural, equivalent notions of a “shortest” path. This work generalizes previous results for simply connected domains with simple closed curve boundaries.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
