Computing fundamental groups from point clouds

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 (Formula Presented.)-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 (Formula Presented.) of a metric space (Formula Presented.) using only a finite point cloud (Formula Presented.) sampled from the space. In the special case where (Formula Presented.) is a (Formula Presented.)-dimensional compact manifold (Formula Presented.), we consider the closure of the complement of (Formula Presented.)-sphere (Formula Presented.). For a base-point (Formula Presented.) in the boundary (Formula Presented.) of the manifold (Formula Presented.) one can attempt to determine, from the point cloud (Formula Presented.), the induced homomorphism of fundamental groups (Formula Presented.) in the category of finitely presented groups. We illustrate a computer implementation for (Formula Presented.) a small closed tubular neighbourhood of a tame knot in (Formula Presented.). In this case the homomorphism (Formula Presented.) 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 (Formula Presented.). In particular, the first integral homology of subgroups (Formula Presented.) 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.