Computing Interesting Topological Features
Show full item record
Files in this item
Title: 
Computing Interesting Topological Features 
Author(s): 
Chambers, Erin Wolf

Subject(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 NPHard. 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 ksimplex. We prove that the projection map which takes each ksimplex 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. 
Issue Date: 
200902 
Genre: 
Technical Report 
Type: 
Text 
URI: 
http://hdl.handle.net/2142/11523

Other Identifier(s): 
UIUCDCSR20083036 
Rights Information: 
You are granted permission for the noncommercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (fortyfive) days from the most recent time that you verified that this technical report is still available from the University of Illinois at UrbanaChampaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s). 
Date Available in IDEALS: 
20090423 
Items in IDEALS are protected by copyright, with all rights reserved, unless otherwise indicated.
This item appears in the following Collection(s)
Show full item record
Item Statistics
 Total Downloads: 110
 Downloads this Month: 0
 Downloads Today: 0