Peer-Reviewed Journal Details
Mandatory Fields
Authors
Brendel, P,Dlotko, P,Ellis, G,Juda, M,Mrozek, M
Year
2015
Month
March
Journal
Applicable Algebra In Engineering Communication And Computing
Title
Computing fundamental groups from point clouds
Status
Published
Times Cited
WOS: 4
()
Optional Fields
Search Keyword
Computation Finite presentation Fundamental group Regular cw-complex Discrete Morse theory CELL COMPLEXES
Volume
26
Issue
Start Page
27
End Page
48
Abstract
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.
ISBN / ISSN
Edition
URL
DOI Link
10.1007/s00200-014-0244-1
Grant Details
Funding Body
Grant Details
Publication Themes
Theme (s)