skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: From Curves to Words
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
Award ID(s):
1664858
PAR ID:
10435938
Author(s) / Creator(s):
; ; ; ;
Date Published:
Journal Name:
Young Researcher's Forum at CG Week
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; (, Proceedings Algorithms and Data Structures: 18th International Symposium, WADS)
    Morin, Pat; Suri, Subhash (Ed.)
    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
  2. ; (, Symmetry, Integrability and Geometry: Methods and Applications)
    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
  3. ; ; (, International Mathematics Research Notices)
    Abstract We apply the method of orbit harmonics to the set of break divisors and orientable divisors on graphs to obtain the central and external zonotopal algebras, respectively. We then relate a construction of Efimov in the context of cohomological Hall algebras to the central zonotopal algebra of a graph $$G_{Q,\gamma }$$ constructed from a symmetric quiver $$Q$$ with enough loops and a dimension vector $$\gamma $$. This provides a concrete combinatorial perspective on the former work, allowing us to identify the quantum Donaldson–Thomas (DT) invariants as the Hilbert series of the space of $$S_{\gamma }$$-invariants of the Postnikov–Shapiro slim subgraph space attached to $$G_{Q,\gamma }$$. The connection with orbit harmonics in turn allows us to give a manifestly nonnegative combinatorial interpretation to numerical DT invariants as the number of $$S_{\gamma }$$-orbits under the permutation action on the set of break divisors on $$G$$. We conclude with several representation-theoretic consequences, whose combinatorial ramifications may be of independent interest. 
    more » « less
  4. ; ; ; (, Discrete & Computational Geometry)
    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
  5. ; (, Developmental Science)
    Holistic processing (HP) of faces refers to the obligatory, simultaneous processing of the parts and their relations, and it emerges over the course of development. HP is manifest in a decrement in the perception of inverted versus upright faces and a reduction in face processing ability when the relations between parts are perturbed. Here, adopting the HP framework for faces, we examined the developmental emergence of HP in another domain for which human adults have expertise, namely, visual word processing. Children, adolescents, and adults performed a lexical decision task and we used two established signatures of HP for faces: the advantage in perception of upright over inverted words and nonwords and the reduced sensitivity to increasing parts (word length). Relative to the other groups, children showed less of an advantage for upright versus inverted trials and lexical decision was more affected by increasing word length. Performance on these HP indices was strongly associated with age and with reading proficiency. Also, the emergence of HP for word perception was not simply a result of improved visual perception over the course of development as no group differences were observed on an object decision task. These results reveal the developmental emergence of HP for orthographic input, and reflect a further instance of experience-dependent tuning of visual perception. These results also add to existing findings on the commonalities of mechanisms of word and face recognition. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email