Document Open Access Logo

The Multi-cover Persistence of Euclidean Balls

Authors Herbert Edelsbrunner, Georg Osang

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.34.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Herbert Edelsbrunner
Georg Osang

Cite AsGet BibTex

Herbert Edelsbrunner and Georg Osang. The Multi-cover Persistence of Euclidean Balls. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SoCG.2018.34

Abstract

Given a locally finite X subseteq R^d and a radius r >= 0, the k-fold cover of X and r consists of all points in R^d that have k or more points of X within distance r. We consider two filtrations - one in scale obtained by fixing k and increasing r, and the other in depth obtained by fixing r and decreasing k - and we compute the persistence diagrams of both. While standard methods suffice for the filtration in scale, we need novel geometric and topological concepts for the filtration in depth. In particular, we introduce a rhomboid tiling in R^{d+1} whose horizontal integer slices are the order-k Delaunay mosaics of X, and construct a zigzag module from Delaunay mosaics that is isomorphic to the persistence module of the multi-covers.
Keywords
  • Delaunay mosaics
  • hyperplane arrangements
  • discrete Morse theory
  • zigzag modules
  • persistent homology

Metrics

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

References

  1. Franz Aurenhammer. A new duality result concerning Voronoi diagrams. Discrete &Computational Geometry, 5(3):243-254, 1990. Google Scholar
  2. Franz Aurenhammer and Otfried Schwarzkopf. A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams. International Journal of Computational Geometry &Applications, 2(04):363-381, 1992. Google Scholar
  3. Ulrich Bauer and Herbert Edelsbrunner. The Morse theory of Čech and Delaunay complexes. Trans. Amer. Math. Soc., 369(369):3741-3762, 2017. Google Scholar
  4. Gunnar Carlsson and Vin de Silva. Zigzag persistence. Found. Comput. Math., 10(4):367-405, 2010. Google Scholar
  5. Gunnar Carlsson, Vin De Silva, and Dmitriy Morozov. Zigzag persistent homology and real-valued functions. In Proceedings of the twenty-fifth annual symposium on Computational geometry, pages 247-256. ACM, 2009. Google Scholar
  6. Frédéric Chazal, David Cohen-Steiner, and Quentin Mérigot. Geometric inference for probability measures. Found. Comput. Math., 11(6):733-751, 2011. Google Scholar
  7. Herbert Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, Heidelberg, Germany, 1987. Google Scholar
  8. Herbert Edelsbrunner and John L. Harer. Computational Topology. An Introduction. American Mathematical Society, Providence, RI, 2010. Google Scholar
  9. Herbert Edelsbrunner, Anton Nikitenko, and Georg Osang. A step in the weighted Delaunay mosaic of order k., 2017. Manuscript, IST Austria, Klosterneuburg, Austria. Google Scholar
  10. Herbert Edelsbrunner and Raimund Seidel. Voronoi diagrams and arrangements. Discrete Comput. Geom., 1(1):25-44, 1986. Google Scholar
  11. G. Fejes Tóth. Multiple packing and covering of the plane with circles. Acta Math. Acad. Sci. Hungar., 27(1-2):135-140, 1976. Google Scholar
  12. Robin Forman. Morse theory for cell complexes. Adv. Math., 134(1):90-145, 1998. Google Scholar
  13. Ragnar Freij. Equivariant discrete Morse theory. Discrete Math., 309(12):3821-3829, 2009. Google Scholar
  14. Leonidas Guibas, Dmitriy Morozov, and Quentin Mérigot. Witnessed k-distance. Discrete Comput. Geom., 49(1):22-45, 2013. Google Scholar
  15. Dmitry Krasnoshchekov and Valentin Polishchuk. Order-k α-hulls and α-shapes. Inform. Process. Lett., 114(1-2):76-83, 2014. Google Scholar
  16. Der-Tsai Lee et al. On k-nearest neighbor Voronoi diagrams in the plane. IEEE Trans. Comput., 31(6):478-487, 1982. Google Scholar
  17. Jean Leray. Sur la forme des espaces topologiques et sur les points fixes des représentations. J. Math. Pures Appl. (9), 24:95-167, 1945. Google Scholar
  18. Michael Lesnick and Matthew Wright. Interactive visualization of 2-D persistence modules. arXiv preprint arXiv:1512.00180, 2015. Google Scholar
  19. Ketan Mulmuley. Output sensitive construction of levels and Voronoi diagrams in ℝ^d of order 1 to k. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 322-330. ACM, 1990. Google Scholar
  20. Michael Ian Shamos and Dan Hoey. Closest-point problems. In 16th Annual Symposium on Foundations of Computer Science (Berkeley, Calif., 1975), pages 151-162. IEEE Computer Society, Long Beach, Calif., 1975. Google Scholar
  21. Donald R. Sheehy. A multi-cover nerve for geometric inference. In Proc. Canadian Conf. Comput. Geom., 2012. 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 Imprint Privacy Contact