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

Abstract:

The(Vietoris-)Rips complexof a discrete point-setPis an abstract simplicial complex in which a subset ofPdefines 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(mlogn) time to preprocess a set ofnpoints in the plane in whichmpairs have distance at most 1; after preprocessing, deciding whether a cycle ofkRips 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^{2}logn+mn) time.

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