Efficient construction of the Čech complex

Dantchev, Stefan; Ivrissimtzis, Ioannis

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.

Citation

Dantchev, S., & Ivrissimtzis, I. (2012). Efficient construction of the Čech complex. Computers and Graphics, 36(6), 708-713. https://doi.org/10.1016/j.cag.2012.02.016

• Journal Article Type: Article
• Acceptance Date: Feb 29, 2012
• Online Publication Date: Mar 9, 2012
• Publication Date: Mar 9, 2012
• Deposit Date: Jun 17, 2019
• Publicly Available Date: Jun 17, 2019
• Journal: Computers and Graphics
• Print ISSN: 0097-8493
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 36
• Issue: 6
• Pages: 708-713
• DOI: https://doi.org/10.1016/j.cag.2012.02.016