An algorithm for calculating top-dimensional bounding chains

Authors

J. Frederico Carvalho​, Royal Institute of Technology
Mikael Vejdemo-Johansson, CUNY College of Staten IslandFollow
Danica Kragic, Royal Institute of Technology
Florian T. Pokorny, Royal Institute of Technology

Document Type

Article

Publication Date

5-28-2018

Abstract

We describe the Coefficient-Flow algorithm for calculating the bounding chain of an (n-1)-boundary on an n-manifold-like simplicial complex S. We prove its correctness and show that it has a computational time complexity of O(|S(n−1)|) (where S(n−1) is the set of (n-1)-faces of S). We estimate the big-O coefficient which depends on the dimension of S and the implementation. We present an implementation, experimentally evaluate the complexity of our algorithm, and compare its performance with that of solving the underlying linear system.

Comments

This work was originally published in PeerJ Computer Science available at https://doi.org/10.7717/peerj-cs.153

This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, reproduction and adaptation in any medium and for any purpose provided that it is properly attributed.