Testing contractibility in planar Rips complexes

Written with Erin Wolf Chambers* and Pratik Worah*.

Proceedings of the 24th Annual ACM Symposium on Computational Geometry, 251-259, 2008.

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(n2 log n + mn) time.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 21 Jan 2012