Peer-Reviewed Journal Details
Mandatory Fields
Brendel, P,Dlotko, P,Ellis, G,Juda, M,Mrozek, M
Applicable Algebra In Engineering Communication And Computing
Computing fundamental groups from point clouds
Optional Fields
Computation Finite presentation Fundamental group Regular cw-complex Discrete Morse theory CELL COMPLEXES
We describe an algorithm for computing a finite, and typically small, presentation of the fundamental group of a finite regular CW-space. The algorithm is based on the construction of a discrete vector field on the -skeleton of the space. A variant yields the homomorphism of fundamental groups induced by a cellular map of spaces. We illustrate how the algorithm can be used to infer information about the fundamental group of a metric space using only a finite point cloud sampled from the space. In the special case where is a -dimensional compact manifold , we consider the closure of the complement of in the -sphere . For a base-point in the boundary of the manifold one can attempt to determine, from the point cloud , the induced homomorphism of fundamental groups in the category of finitely presented groups. We illustrate a computer implementation for a small closed tubular neighbourhood of a tame knot in . In this case the homomorphism is known to be a complete ambient isotopy invariant of the knot. We observe that low-index subgroups of finitely presented groups provide useful invariants of . In particular, the first integral homology of subgroups of index at most six suffices to distinguish between all prime knots with 11 or fewer crossings (ignoring chirality). We plan to provide formal time estimates for our algorithm and characteristics of a high performance C++ implementation in a subsequent paper. The prototype computer implementation of the present paper has been written in the interpreted gap programming language for computational algebra.
Grant Details
Publication Themes