Geometry-driven collapses for converting a Cech complex into a triangulation of a nicely triangulable shape

24 pages, 9 figuresInternational audienceGiven a set of points that sample a shape, the Rips complex of the points is often used to provide an approximation of the shape easily-computed. It has been proved that the Rips complex captures the homotopy type of the shape, assuming that the vertices of the complex meet some mild sampling conditions. Unfortunately, the Rips complex is generally high-dimensional. To remedy this problem, it is tempting to simplify it through a sequence of collapses. Ideally, we would like to end up with a triangulation of the shape. Experiments suggest that, as we simplify the complex by iteratively collapsing faces, it should indeed be possible to avoid entering a dead end such as the famous Bing’s house with two rooms. This paper provides a theoretical justification for this empirical observation. We demonstrate that the Rips complex of a point cloud (for a well-chosen scale parameter) can always be turned into a simplicial complex homeomorphic to the shape by a sequence of collapses, assuming that the shape is nicely triangulable and well-sampled (two concepts we will explain in the paper). To establish our result, we rely on a recent work which gives conditions under which the Rips complex can be converted into a Čech complex by a sequence of collapses. We proceed in two phases. Starting from the Čech complex, we first produce a sequence of collapses that arrives to the Čech complex, restricted by the shape. We then apply a sequence of collapses that transforms the result into the nerve of some covering of the shape. Along the way, we establish results which are of independent interest. First, we show that the reach of a shape cannot decrease when intersected with a (possibly infinite) collection of balls, assuming the balls are small enough. Under the same hypotheses, we show that the restriction of a shape with respect to an intersection of balls is either empty or contractible. We also provide conditions under which the nerve of a family of compact sets undergoes collapses as the compact sets evolve over time. We believe conditions are general enough to be useful in other contexts as well