Testing contractibility in planar Rips complexes

Submitted to the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (2008).

• Download submitted SODA version:

Abstract:

The (Vietoris-)Rips complex of a discrete point-set P is an abstract simplicial complex in which a subset of P defines a simplex if and only if the diameter of that subset is at most 1. We describe an efficient algorithm to determine whether a given cycle in a planar Rips complex is contractible. Our algorithm requires O(m log n) time to preprocess a set of n points in the plane in which m pairs have distance at most 1; after preprocessing, deciding whether a cycle of k Rips edges is contractible requires O(k) time. We also describe an algorithm to compute the shortest non-contractible cycle in a planar Rips complex in O(n² log n + mn) time.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 03 Dec 2008