@inproceedings{456bf3b78d2140d28782082d068b90e4,
title = "Testing contractibility in planar rips complexes",
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(n2 log n + mn) time.",
keywords = "Computational topology, Homotopy, Rips shadow, Vietoris-rips complex",
author = "Chambers, {Erin W.} and Jeff Erickson and Pratik Worah",
year = "2008",
doi = "10.1145/1377676.1377721",
language = "English (US)",
isbn = "9781605580715",
series = "Proceedings of the Annual Symposium on Computational Geometry",
pages = "251--259",
booktitle = "Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08",
note = "24th Annual Symposium on Computational Geometry, SCG'08 ; Conference date: 09-06-2008 Through 11-06-2008",
}