Efficient construction of the Čech complex

In many applications, the first step into the topological analysis of a discrete point set P sampled from a manifold is the construction of a simplicial complex with vertices on P. In this paper, we present an algorithm for the efficient computation of the Čech complex of P   for a given value εε of the radius of the covering balls. Experiments show that the proposed algorithm can generally handle input sets of several thousand points, while for the topologically most interesting small values of εε can handle inputs with tens of thousands of points. We also present an algorithm for the construction of all possible Čech complices on P.

Figure optionsDownload high-quality image (191 K)Download as PowerPoint slideHighlights
► A heuristic algorithm is presented that creates the Čech complex of given points.
► The algorithm achieves empirically good running times on reasonable-size data sets.
► A decremental algorithm is presented that creates all complices at different scales.