Testing contractibility in planar rips complexes Export

@inproceedings{citeulike:4722974, 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 2 log n + mn ) time.}, address = {New York, NY, USA}, author = {Chambers, Erin W. and Erickson, Jeff and Worah, Pratik}, booktitle = {SCG '08: Proceedings of the twenty-fourth annual symposium on Computational geometry}, citeulike-article-id = {4722974}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1377676.1377721}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1377676.1377721}, doi = {10.1145/1377676.1377721}, isbn = {978-1-60558-071-5}, keywords = {algorithms, stochastic, testing, topology}, location = {College Park, MD, USA}, pages = {251--259}, posted-at = {2009-06-02 21:16:24}, priority = {2}, publisher = {ACM}, title = {Testing contractibility in planar rips complexes}, url = {http://dx.doi.org/10.1145/1377676.1377721}, year = {2008} }

TY - CONF ID - citeulike:4722974 L3 - citeulike-article-id:4722974 N2 - 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 2 log n + mn ) time. CY - College Park, MD, USA SN - 978-1-60558-071-5 AD - New York, NY, USA EP - 259 TI - Testing contractibility in planar rips complexes PB - ACM T2 - SCG '08: Proceedings of the twenty-fourth annual symposium on Computational geometry SP - 251 KW - algorithms KW - stochastic KW - testing KW - topology AU - Chambers, Erin AU - Erickson, Jeff AU - Worah, Pratik PY - 2008/// UR - http://dx.doi.org/10.1145/1377676.1377721 ER -