Computing Interesting Topological Features

Chambers, Erin Wolf

Permalink

https://hdl.handle.net/2142/11523 Copy

Description

Title

Computing Interesting Topological Features

Author(s)

Chambers, Erin Wolf

Issue Date

2009-02

Keyword(s)

algorithms

Abstract

"Many questions about homotopy are provably hard or even unsolvable in general. However, in specific settings, it is possible to efficiently test homotopyequivalence or compute shortest cycles with prescribed homotopy. We focus on computing such ""interesting"" topological features in three settings. The first two results are about cycles on surfaces; the third is about classes of homotopies in IR2 minus a set of obstacles; and the final result is about paths and cycles in Rips complexes. First, we examine two problems in the combinatorial surface model. Combinatorial surfaces combine properties of graphs and manifolds, making a rich set of techniques available for analysis and algorithm design. We give algorithms to find the shortest noncontractible and nonseparating cycles in a combinatorial surface in O(g3n log n) time. Our main tool is a data structure that kinetically maintains the shortest path tree as the root of the tree moves around the vertices of a single face. The total running time is O(g2n log n). By maintaining the data structure persistently, we can answer shortest path queries in O(log n) time. Next we consider finding the shortest splitting cycle in a combinatorial surface, or simple cycle which is both separating and noncontractible; such cycles divide the topology of the surface as well as the underlying graph. We prove that finding the shortest splitting cycle is NP-Hard. We then give an algorithm that runs gO(g)n log n time, which is polynomial if the surface is fixed. We then examine a very different setting, namely similarity between curves in some underlying metric space. If we imagine a homotopy between the curves as a way to morph one curve into the other, we can optimize the morphing so that the maximum distance any point must travel is minimized. This is a generalization of the more well known Frechet distance, with the additional requirement that the leash to move continuously in the ambient space. We call this distance the homotopic Frechet distance. We give a polynomial time algorithm to compute the homotopic Fr´echet distance between two curves in the plane minus a set of polygonal obstacles. We also extend our characterization of optimal morphings to surfaces of nonpositive curvature. Finally, we examine a more fundamental homotopy problem in a different setting. A Rips complex is a simplicial complex defined by a set of points from ii some metric space where every pair of points within distance 1 is connected by an edge, and every (k + 1)-clique in that graph forms a k-simplex. We prove that the projection map which takes each k-simplex in the Rips complex to the convex hull of the original points in the plane induces an isomorphism between the fundamental groups of both spaces. Since the union of these convex hulls is a polygonal region in the plane, possibly with holes, our result implies that the fundamental group of a planar Rips complex is a free group, allowing us to design efficient algorithms to answer homotopy questions in planar Rips complexes."

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11523

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections