Persistent homology in _ metric

DOI10.1016/J.COMGEO.2021.101821MaRDI QIDQ2064022zbMATH OpenOpenAlexFDO

Authors Gabriele Beltramo, Primoz Skraba

Publication date 3 January 2022

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.02071

zbMATH Keywords

Chebyshev distanceDelaunay triangulationpersistent homologytopological data analysis

Mathematics Subject Classification ID

Persistent homology and applications, topological data analysis (55N31) Other homology theories in algebraic topology (55N35) Simplicial sets and complexes in algebraic topology (55U10) General topology of complexes (57Q05) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Proximity complexes and filtrations are central constructions in topological data analysis. Built using distance functions, or more generally metrics, they are often used to infer connectivity information from point clouds. Here we investigate proximity complexes and filtrations built over the Chebyshev metric, also known as the maximum metric or $el{l}_{infty}$ metric, rather than the classical Euclidean metric. Somewhat surprisingly, the $el{l}_{infty}$ case has not been investigated thoroughly. In this paper, we examine a number of classical complexes under this metric, including the v{C}ech, Vietoris-Rips, and Alpha complexes. We define two new families of flag complexes, which we call the Alpha flag and Minibox complexes, and prove their equivalence to v{C}ech complexes in homological degrees zero and one. Moreover, we provide algorithms for finding Minibox edges of two, three, and higher-dimensional points. Finally, we present computational experiments on random points, which shows that Minibox filtrations can often be used to speed up persistent homology computations in homological degrees zero and one by reducing the number of simplices in the filtration.

Review text

Based on the \(l_{\infty}\)-metric, the paper examines a number of classical complexes, including the Čech, Vietoris-Rips, and Alpha complexes. ``We define two new families of flag complexes, the Alpha flag and Minibox complexes, and prove their equivalence to Čech complexes in homological degrees zero and one. Moreover, we provide algorithms for finding Minibox edges of two, three, and higher-dimensional points. Besides, using this algorithm, the paper presents computational experiments on random points. This approach can be useful to compute persistent homology of a complex.

Recommendations

• Persistence stability for geometric complexes
• Topological inference via meshing
• Improved approximate Rips filtrations with shifted integer lattices

Cites work

• An O(n log n) plane-sweep algorithm for \(L_ 1\) and \(L_{\infty}\) Delaunay triangulations
• Barcodes: The persistent topology of data
• Clear and compress: computing persistent homology in chunks
• Computational topology. An introduction
• Computing persistent homology
• Distributed computation of persistent homology
• Dualities in persistent (co)homology
• Efficient Computation of Persistent Homology for Cubical Data
• Fast algorithms for direct enclosures and direct dominances
• Higher-dimensional Voronoi diagrams in linear expected time
• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• scientific article; zbMATH DE number 830463 (Why is no real title available?)
• scientific article; zbMATH DE number 6297698 (Why is no real title available?)
• Improved approximate Rips filtrations with shifted integer lattices
• Maximal empty boxes amidst random points
• Morse theory for filtrations and efficient computation of persistent homology
• On rectangular visibility
• On the Average Number of Maxima in a Set of Vectors and Applications
• Persistence stability for geometric complexes
• Persistence theory. From quiver representations to data analysis
• Persistent homology -- a survey
• Priority Search Trees
• Ripser: efficient computation of Vietoris-Rips persistence barcodes
• Stability of persistence diagrams
• Stochastic and Integral Geometry
• The Morse Theory of Čech and Delaunay Filtrations
• The Offset Filtration of Convex Objects
• Three-dimensional alpha shapes
• Topological persistence and simplification
• Topology and data
• Voronoi diagrams and Delaunay triangulations
• Voronoi diagrams in higher dimensions under certain polyhedral distance functions
• Zigzag persistent homology in matrix multiplication time

Cited in

(7)

• A complete characterization of the one-dimensional intrinsic Čech persistence diagrams for metric graphs
• Relative persistent homology
• Footprints of geodesics in persistent homology
• \(p\)-cyclic persistent homology and Hofer distance
• Persistent homology of the sum metric
• Optimising the topological information of the \(A_\infty \)-persistence groups
• On the persistent homology of almost surely C^0 stochastic processes

Describes a project that uses

Uses Software

• giotto-ph
• Ripser

This page was built for publication: Persistent homology in \(\ell_\infty\) metric

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2064022)