Document Open Access Logo

Computing the Multicover Bifiltration

Authors René Corbet , Michael Kerber , Michael Lesnick , Georg Osang

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.27.pdf
  • Filesize: 1.3 MB
  • 17 pages

Document Identifiers

Author Details

René Corbet
  • Department of Mathematics, KTH Royal Institute of Technology, Stockholm, Sweden
Michael Kerber
  • Institute of Geometry, Graz University of Technology, Austria
Michael Lesnick
  • Department of Mathematics and Statistics, University at Albany, SUNY, NY, USA
Georg Osang
  • IST Austria (Institute of Science and Technology Austria), Klosterneuburg, Austria

Funding

The first two authors were supported by the Austrian Science Fund (FWF) grant number P 29984-N35 and W1230. The first author was partly supported by an Austrian Marshall Plan Scholarship, and by the Brummer & Partners MathDataLab.

Acknowledgements

The authors want to thank the reviewers for many helpful comments and suggestions.

Cite As Get BibTex

René Corbet, Michael Kerber, Michael Lesnick, and Georg Osang. Computing the Multicover Bifiltration. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.SoCG.2021.27

Abstract

Given a finite set A ⊂ ℝ^d, let Cov_{r,k} denote the set of all points within distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter family of spaces that grow larger when r increases or k decreases, called the multicover bifiltration. Motivated by the problem of computing the homology of this bifiltration, we introduce two closely related combinatorial bifiltrations, one polyhedral and the other simplicial, which are both topologically equivalent to the multicover bifiltration and far smaller than a Čech-based model considered in prior work of Sheehy. Our polyhedral construction is a bifiltration of the rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using a variant of an algorithm given by these authors as well. Using an implementation for dimension 2 and 3, we provide experimental results. Our simplicial construction is useful for understanding the polyhedral construction and proving its correctness.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial algorithms
  • Theory of computation → Computational geometry
Keywords
  • Bifiltrations
  • nerves
  • higher-order Delaunay complexes
  • higher-order Voronoi diagrams
  • rhomboid tiling
  • multiparameter persistent homology
  • denoising

Metrics

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

Related Versions

References

  1. Hirokazu Anai, Frédéric Chazal, Marc Glisse, Yuichi Ike, Hiroya Inakoshi, Raphaël Tinarrage, and Yuhei Umeda. DTM-based filtrations. In 35th International Symposium on Computational Geometry (SoCG 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.SoCG.2019.58.
  2. Franz Aurenhammer. Power diagrams: properties, algorithms and applications. SIAM Journal on Computing, 16(1):78-96, 1987. URL: https://doi.org/10.1137/0216006.
  3. Ulrich Bauer, Michael Kerber, Fabian Roll, and Alexander Rolle. A unified view on nerve theorems. Unpublished manuscript, 2020. Google Scholar
  4. Andrew J. Blumberg, Itamar Gal, Michael A. Mandell, and Matthew Pancia. Robust statistics, hypothesis testing, and confidence intervals for persistent homology on metric measure spaces. Foundations of Computational Mathematics, 14(4):745-789, 2014. URL: https://doi.org/10.1007/s10208-014-9201-4.
  5. Andrew J. Blumberg and Michael Lesnick. Universality of the homotopy interleaving distance, 2017. URL: http://arxiv.org/abs/1705.01690.
  6. Andrew J. Blumberg and Michael Lesnick. Stability of 2-parameter persistent homology, 2020. URL: http://arxiv.org/abs/2010.09628.
  7. Omer Bobrowski, Sayan Mukherjee, Jonathan E. Taylor, et al. Topological consistency via kernel estimation. Bernoulli, 23(1):288-328, 2017. URL: https://doi.org/10.3150/15-BEJ744.
  8. Mickaël Buchet, Frédéric Chazal, Steve Y. Oudot, and Donald R. Sheehy. Efficient and robust persistent homology for measures. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA 2015), pages 168-180. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973730.13.
  9. Gunnar Carlsson, Tigran Ishkhanov, Vin De Silva, and Afra Zomorodian. On the local behavior of spaces of natural images. International journal of computer vision, 76(1):1-12, 2008. URL: https://doi.org/10.1007/s11263-007-0056-x.
  10. Gunnar Carlsson and Afra Zomorodian. The theory of multidimensional persistence. Discrete & Computational Geometry, 42(1):71-93, 2009. URL: https://doi.org/10.1007/s00454-009-9176-0.
  11. Nicholas J. Cavanna, Kirk P. Gardner, and Donald R. Sheehy. When and why the topological coverage criterion works. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA 2017), 2017. URL: https://doi.org/10.1137/1.9781611974782.177.
  12. Nicholas J. Cavanna, Mahmoodreza Jahanseir, and Donald R. Sheehy. A geometric perspective on sparse filtrations. In Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG 2015), 2015. Google Scholar
  13. Andrea Cerri, Barbara Di Fabio, Massimo Ferri, Patrizio Frosini, and Claudia Landi. Betti numbers in multidimensional persistent homology are stable functions. Mathematical Methods in the Applied Sciences, 36(12):1543-1557, 2013. URL: https://doi.org/10.1002/mma.2704.
  14. Frédéric Chazal, Leonidas J. Guibas, Steve Y. Oudot, and Primoz Skraba. Scalar field analysis over point cloud data. Discrete & Computational Geometry, 46(4):743-775, 2011. URL: https://doi.org/10.1007/s00454-011-9360-x.
  15. Frédéric Chazal, Leonidas J. Guibas, Steve Y. Oudot, and Primoz Skraba. Persistence-based clustering in Riemannian manifolds. Journal of the ACM, 60(6), 2013. URL: https://doi.org/10.1145/2535927.
  16. Frédéric Chazal and Steve Y. Oudot. Towards persistence-based reconstruction in Euclidean spaces. In 24th International Symposium on Computational Geometry (SoCG 2008), page 232–241. Association for Computing Machinery (ACM), 2008. URL: https://doi.org/10.1145/1377676.1377719.
  17. Frédéric Chazal, David Cohen-Steiner, and Quentin Mérigot. Geometric inference for probability measures. Foundations of Computational Mathematics, 11:733-751, December 2011. URL: https://doi.org/10.1007/s10208-011-9098-0.
  18. Kenneth L. Clarkson and Peter W. Shor. Applications of random sampling in computational geometry, II. Discrete & Computational Geometry, 4(5):387-421, 1989. URL: https://doi.org/10.1007/BF02187740.
  19. David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. Discrete & Computational Geometry, 37(1):103-120, 2007. URL: https://doi.org/10.1007/s00454-006-1276-5.
  20. Tamal K. Dey and Cheng Xin. Generalized persistence algorithm for decomposing multi-parameter persistence modules, 2020. URL: http://arxiv.org/abs/1904.03766.
  21. William G. Dwyer and Jan Spalinski. Homotopy theories and model categories. Handbook of algebraic topology, 73:126, 1995. URL: https://doi.org/10.1016/B978-044481779-2/50003-1.
  22. Herbert Edelsbrunner. Algorithms in combinatorial geometry. Springer-Verlag, 1987. URL: https://doi.org/10.1007/978-3-642-61568-9.
  23. Herbert Edelsbrunner. The union of balls and its dual shape. Discrete & Computational Geometry, 13(3):415-440, 1995. URL: https://doi.org/10.1007/BF02574053.
  24. Herbert Edelsbrunner. Shape reconstruction with Delaunay complex. In LATIN'98: Theoretical Informatics, pages 119-132. Springer Berlin Heidelberg, 1998. URL: https://doi.org/10.1007/BFb0054315.
  25. Herbert Edelsbrunner and John Harer. Computational topology: an introduction. American Mathematical Society, 2010. URL: https://doi.org/10.1007/978-3-540-33259-6_7.
  26. Herbert Edelsbrunner and Georg Osang. The multi-cover persistence of Euclidean balls. In 34th International Symposium on Computational Geometry (SoCG 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.SoCG.2018.34.
  27. Herbert Edelsbrunner and Georg Osang. A simple algorithm for computing higher order Delaunay mosaics and α-shapes, 2020. URL: http://arxiv.org/abs/2011.03617.
  28. Herbert Edelsbrunner and Raimund Seidel. Voronoi diagrams and arrangements. Discrete & Computational Geometry, 1(1):25-44, 1986. URL: https://doi.org/10.1007/BF02187681.
  29. Leonidas Guibas, Dmitriy Morozov, and Quentin Mérigot. Witnessed k-distance. Discrete & Computational Geometry, 49(1):22-45, 2013. URL: https://doi.org/10.1007/s00454-012-9465-x.
  30. Heather A. Harrington, Nina Otter, Hal Schenck, and Ulrike Tillmann. Stratifying multiparameter persistent homology, 2017. URL: http://arxiv.org/abs/1708.07390.
  31. Allen Hatcher. Algebraic Topology. Cambridge University Press, 2005. Google Scholar
  32. Philip S. Hirschhorn. Model categories and their localizations, volume 99. American Mathematical Society, 2009. Google Scholar
  33. Derek F. Holt. The Meataxe as a tool in computational group theory. London Mathematical Society Lecture Note Series, pages 74-81, 1998. Google Scholar
  34. Michael Kerber and Alexander Rolle. Fast minimal presentations of bi-graded persistence modules. In 2021 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), pages 207-220. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976472.16.
  35. Dmitry Kozlov. Combinatorial Algebraic Topology. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-71962-5.
  36. Dmitry Krasnoshchekov and Valentin Polishchuk. Order-k alpha-hulls and alpha-shapes. Information Processing Letters, 114(1-2):76-83, 2014. URL: https://doi.org/10.1016/j.ipl.2013.07.023.
  37. Edoardo Lanari and Luis N. Scoccola. Rectification of interleavings and a persistent Whitehead theorem, 2020. URL: http://arxiv.org/abs/2010.05378.
  38. Jean Leray. Sur la forme des espaces topologiques et sur les points fixes des representations. Journal de Mathématiques Pures et Appliquées, 24, January 1945. Google Scholar
  39. Michael Lesnick and Matthew Wright. Interactive visualization of 2-D persistence modules, 2015. URL: http://arxiv.org/abs/1512.00180.
  40. Michael Lesnick and Matthew Wright. Computing minimal presentations and Betti numbers of 2-parameter persistent homology, 2019. URL: http://arxiv.org/abs/1902.05708.
  41. Georg F. Osang. Multi-cover persistence and Delaunay mosaics. PhD thesis, IST Austria, 2021. URL: https://doi.org/10.15479/AT:ISTA:9056.
  42. Jeff M. Phillips, Bei Wang, and Yan Zheng. Geometric inference on kernel density estimates. In 31st International Symposium on Computational Geometry (SoCG 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. URL: https://doi.org/10.4230/LIPIcs.SOCG.2015.857.
  43. Luis N. Scoccola. Locally Persistent Categories And Metric Properties Of Interleaving Distances. PhD thesis, The University of Western Ontario, 2020. URL: https://ir.lib.uwo.ca/etd/7119/.
  44. Donald R. Sheehy. A multicover nerve for geometric inference. In Proceedings of the 24th Canadian Conference in Computational Geometry (CCCG 2012), 2012. Google Scholar
  45. Donald R. Sheehy. Linear-size approximations to the Vietoris-Rips filtration. Discrete & Computational Geometry, 49(4):778-796, 2013. URL: https://doi.org/10.1007/s00454-013-9513-1.
  46. Donald R. Sheehy. A sparse delaunay filtration, 2020. URL: http://arxiv.org/abs/2012.01947.
  47. Oliver Vipond. Multiparameter persistence landscapes. Journal of Machine Learning Research, 21(61):1-38, 2020. URL: http://jmlr.org/papers/v21/19-054.html.
  48. Georgy Voronoi. Recherches sur les paralléloèdres primitives. Journal für die reine und angewandte Mathematik, 134:198-287, 1908. Google Scholar
  49. Afra Zomorodian and Gunnar Carlsson. Computing persistent homology. Discrete and Computational Geometry, 33(2):249-274, 2005. URL: https://doi.org/10.1007/s00454-004-1146-y.
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