An improved algorithm for Generalized Čech complex construction

Abstract

In this paper, we present an algorithm that computes the generalized Čech complex for a finite set of disks where each may have a different radius in 2D space. An extension of this algorithm is also proposed for a set of balls in 3D space with different radius. To compute a $k$-simplex, we leverage the computation performed in the round of $(k-1)$-simplices such that we can reduce the number of potential candidates to verify to improve the efficiency. An efficient verification method is proposed to confirm if a $k$-simplex can be constructed on the basis of the $(k-1)$-simplices. We demonstrate the performance with a comparison to some closely related algorithms.