Efficient construction of the Čech complex

Abstract: 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. [Copyright &y& Elsevier]