Testing contractibility in planar rips complexes

2008/06/09 by Erin Wolf Chambers, Jeff Erickson, Pratik Worah · 1 citation
Computer Science · Mathematics · #Topological and Geometric Data Analysis #Computational Geometry and Mesh Generation #Advanced Combinatorial Mathematics #Contractible space #Simplicial complex #Simplex #Combinatorics #Mathematics #Planar #Preprocessor #Set (abstract data type) #Point (geometry) #Plane (geometry) #Discrete mathematics #Algorithm #Computer science #Artificial intelligence #Geometry

paper · doi:10.1145/1377676.1377721

openalex publication_date 2008/06/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

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

Citations

• Finding Shortest Non-Separating and Non-Contractible Cycles for Topologically Embedded Graphs
• Rips Complexes of Planar Point Sets
• Vietoris-Rips complexes of metric spaces near a closed Riemannian manifold
• Transforming Curves on Surfaces
• �ber den h�heren Zusammenhang kompakter R�ume und eine Klasse von zusammenhangstreuen Abbildungen
• Computing crossing number in linear time
• The union of balls and its dual shape
• AN ALGEBRAIC TOPOLOGICAL METHOD FOR FEATURE IDENTIFICATION
• The LCA Problem Revisited
• Computing Persistent Homology
• Topological Persistence and Simplification

Cited by

• Vietoris–Rips complex [wikipedia]