Document Open Access Logo

Improved Approximate Rips Filtrations with Shifted Integer Lattices

Authors Aruni Choudhary, Michael Kerber, Sharath Raghvendra

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.28.pdf
  • Filesize: 0.84 MB
  • 13 pages

Document Identifiers

Author Details

Aruni Choudhary
Michael Kerber
Sharath Raghvendra

Cite As Get BibTex

Aruni Choudhary, Michael Kerber, and Sharath Raghvendra. Improved Approximate Rips Filtrations with Shifted Integer Lattices. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.28

Abstract

Rips complexes are important structures for analyzing topological features of metric spaces. Unfortunately, generating these complexes constitutes an expensive task because of a combinatorial explosion in the complex size. For n points in R^d, we present a scheme to construct a 4.24-approximation of the multi-scale filtration of the Rips complex in the L-infinity metric, which extends to a O(d^{0.25})-approximation of the Rips filtration for the Euclidean case. The k-skeleton of the resulting approximation has a total size of n2^{O(d log k)}. The scheme is based on the integer lattice and on the barycentric subdivision of the d-cube.

Subject Classification

Keywords
  • Persistent homology
  • Rips filtrations
  • Approximation algorithms
  • Topological Data Analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. M. Botnan and G. Spreemann. Approximating Persistent Homology in Euclidean space through collapses. Applied Algebra in Engineering, Communication and Computing, 26(1-2):73-101, 2015. Google Scholar
  2. P. Bubenik, V. de Silva, and J. Scott. Metrics for Generalized Persistence Modules. Foundations of Computational Mathematics, 15(6):1501-1531, 2015. Google Scholar
  3. P. Bubenik and J.A. Scott. Categorification of Persistent Homology. Discrete &Computational Geometry, 51(3):600-627, 2014. Google Scholar
  4. G. Carlsson. Topology and Data. Bulletin of the American Mathematical Society, 46:255-308, 2009. Google Scholar
  5. N.J. Cavanna, M. Jahanseir, and D. Sheehy. A Geometric Perspective on Sparse Filtrations. In Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG 2015). Google Scholar
  6. F. Chazal, D. Cohen-Steiner, M. Glisse, L.J. Guibas, and S.Y. Oudot. Proximity of Persistence Modules and their Diagrams. In Proceedings of the ACM Symposium on Computational Geometry (SoCG 2009), pages 237-246, 2009. Google Scholar
  7. A. Choudhary, M. Kerber, and S. Raghvendra. Improved approximate rips filtrations with shifted integer lattices. CoRR, abs/1706.07399, 2016. URL: https://arxiv.org/abs/1706.07399.
  8. A. Choudhary, M. Kerber, and S. Raghvendra. Polynomial-sized topological approximations using the Permutahedron. In Proceedings of the 32nd International Symposium on Computational Geometry (SoCG 2016), pages 31:1-31:16, 2016. Google Scholar
  9. T.K. Dey, F. Fan, and Y. Wang. Computing Topological Persistence for Simplicial maps. In Proceedings of the ACM Symposium on Computational Geometry (SoCG 2014), pages 345-354, 2014. Google Scholar
  10. H. Edelsbrunner and J. Harer. Computational Topology - An Introduction. American Mathematical Society, 2010. Google Scholar
  11. H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological Persistence and Simplification. Discrete &Computational Geometry, 28(4):511-533, 2002. Google Scholar
  12. M. Kerber and H. Schreiber. Barcodes of Towers and a Streaming Algorithm for Persistent Homology. In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG), pages 57:1-57:15, 2017. Google Scholar
  13. M. Kerber and R. Sharathkumar. Approximate Čech Complex in Low and High Dimensions. In International Symposium on Algorithms and Computation (ISAAC), pages 666-676, 2013. Google Scholar
  14. S. Khuller and Y. Matias. A Simple Randomized Sieve Algorithm for the Closest-Pair Problem. Information and Computation, 118(1):34-37, 1995. Google Scholar
  15. J.R. Munkres. Elements of algebraic topology. Westview Press, 1984. Google Scholar
  16. D. Sheehy. Linear-size Approximations to the Vietoris-Rips Filtration. Discrete & Computational Geometry, 49(4):778-796, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact