{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T15:19:10Z","timestamp":1720451950487},"reference-count":19,"publisher":"PeerJ","license":[{"start":{"date-parts":[[2018,5,28]],"date-time":"2018-05-28T00:00:00Z","timestamp":1527465600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004063","name":"Knut and Alice Wallenberg Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004063","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004359","name":"Swedish Research Council","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We describe the <jats:sc>Coefficient-Flow<\/jats:sc> 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 <jats:italic>O<\/jats:italic>(|<jats:italic>S<\/jats:italic><jats:sup>(<jats:italic>n<\/jats:italic>\u22121)<\/jats:sup>|) (where <jats:italic>S<\/jats:italic><jats:sup>(<jats:italic>n<\/jats:italic>\u22121)<\/jats:sup> 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.<\/jats:p>","DOI":"10.7717\/peerj-cs.153","type":"journal-article","created":{"date-parts":[[2018,5,28]],"date-time":"2018-05-28T03:22:06Z","timestamp":1527477726000},"page":"e153","source":"Crossref","is-referenced-by-count":3,"title":["An algorithm for calculating top-dimensional bounding chains"],"prefix":"10.7717","volume":"4","author":[{"given":"J. Frederico","family":"Carvalho","sequence":"first","affiliation":[{"name":"CAS\/RPL, KTH, Royal Institute of Technology, Stockholm, Sweden"}]},{"given":"Mikael","family":"Vejdemo-Johansson","sequence":"additional","affiliation":[{"name":"Mathematics Department, City University of New York, College of Staten Island, New York, NY,  United States of America"}]},{"given":"Danica","family":"Kragic","sequence":"additional","affiliation":[{"name":"CAS\/RPL, KTH, Royal Institute of Technology, Stockholm, Sweden"}]},{"given":"Florian T.","family":"Pokorny","sequence":"additional","affiliation":[{"name":"CAS\/RPL, KTH, Royal Institute of Technology, Stockholm, Sweden"}]}],"member":"4443","published-online":{"date-parts":[[2018,5,28]]},"reference":[{"issue":"3","key":"10.7717\/peerj-cs.153\/ref-1","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1007\/s00453-014-9887-3","article-title":"The simplex tree: an efficient data structure for general simplicial complexes","volume":"70","author":"Boissonnat","year":"2014","journal-title":"Algorithmica"},{"key":"10.7717\/peerj-cs.153\/ref-2","doi-asserted-by":"publisher","DOI":"10.1145\/1542362.1542426","article-title":"Minimum cuts and shortest homologous cycles","author":"Chambers","year":"2009"},{"key":"10.7717\/peerj-cs.153\/ref-3","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1111\/cgf.12514","article-title":"Computing minimum area homologies","author":"Chambers","year":"2015"},{"key":"10.7717\/peerj-cs.153\/ref-4","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1145\/2462356.2462375","article-title":"Measuring similarity between curves on 2-manifolds via homotopy area. SoCG \u201913","author":"Chambers","year":"2013"},{"issue":"3","key":"10.7717\/peerj-cs.153\/ref-5","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/s00454-010-9322-8","article-title":"Hardness results for homology localization","volume":"45","author":"Chen","year":"2011","journal-title":"Discrete and Computational Geometry"},{"issue":"2","key":"10.7717\/peerj-cs.153\/ref-6","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1017\/S0308210511001648","article-title":"Improved bound for complexity of matrix multiplication","volume":"143","author":"Davie","year":"2013","journal-title":"Proceedings of the Royal Society of Edinburgh Section A: Mathematics"},{"issue":"4","key":"10.7717\/peerj-cs.153\/ref-7","doi-asserted-by":"publisher","first-page":"1026","DOI":"10.1137\/100800245","article-title":"Optimal homologous cycles, total unimodularity, and linear programming","volume":"40","author":"Dey","year":"2011","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"10.7717\/peerj-cs.153\/ref-8","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90123-5","article-title":"Algorithms for plane representations of acyclic digraphs","volume":"61","author":"Di Battista","year":"1988","journal-title":"Theoretical Computer Science"},{"key":"10.7717\/peerj-cs.153\/ref-9","volume-title":"Computational topology: an introduction","author":"Edelsbrunner","year":"2010"},{"issue":"4","key":"10.7717\/peerj-cs.153\/ref-10","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1007\/s00454-002-2885-2","article-title":"Topological persistence and simplification","volume":"28","author":"Edelsbrunner","year":"2002","journal-title":"Discrete & Computational Geometry"},{"key":"10.7717\/peerj-cs.153\/ref-11","author":"Eigen","year":"2017"},{"issue":"1","key":"10.7717\/peerj-cs.153\/ref-12","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1006\/aima.1997.1650","article-title":"Morse theory for cell complexes","volume":"134","author":"Forman","year":"1998","journal-title":"Advances in Mathematics"},{"key":"10.7717\/peerj-cs.153\/ref-13","article-title":"Matrix computations","author":"Gloub","year":"1996","edition":"3"},{"key":"10.7717\/peerj-cs.153\/ref-14","article-title":"Algebraic topology","author":"Hatcher","year":"2002","edition":"2"},{"issue":"1\u20133","key":"10.7717\/peerj-cs.153\/ref-15","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1177\/0278364915586713","article-title":"Topological trajectory classification with filtrations of simplicial complexes and persistent homology","volume":"35","author":"Pokorny","year":"2016","journal-title":"International Journal of Robotics Research"},{"issue":"3","key":"10.7717\/peerj-cs.153\/ref-16","doi-asserted-by":"publisher","first-page":"1159","DOI":"10.1137\/15M1025955","article-title":"Efficient construction of 2-chains with a prescribed boundary","volume":"55","author":"Rodr\u00edguez","year":"2017","journal-title":"Journal of Numerical Analysis"},{"key":"10.7717\/peerj-cs.153\/ref-17","article-title":"3D: Eulaema meriana bee, Smithsonian gardens","author":"Smithsonian","year":"2013"},{"key":"10.7717\/peerj-cs.153\/ref-18","volume-title":"GUDHI user and reference manual","author":"The GUDHI Project","year":"2015"},{"key":"10.7717\/peerj-cs.153\/ref-19","author":"The Stanford 3D scanning repository","year":"1994"}],"container-title":["PeerJ Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/peerj.com\/articles\/cs-153.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/peerj.com\/articles\/cs-153.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/peerj.com\/articles\/cs-153.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/peerj.com\/articles\/cs-153.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,5,28]],"date-time":"2018-05-28T03:22:15Z","timestamp":1527477735000},"score":1,"resource":{"primary":{"URL":"https:\/\/peerj.com\/articles\/cs-153"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,28]]},"references-count":19,"alternative-id":["10.7717\/peerj-cs.153"],"URL":"https:\/\/doi.org\/10.7717\/peerj-cs.153","archive":["CLOCKSS","LOCKSS","Portico"],"relation":{},"ISSN":["2376-5992"],"issn-type":[{"value":"2376-5992","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,5,28]]},"article-number":"e153"}}