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.