Linear-size approximations to the Vietoris-Rips filtration (Q2391709): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
ReferenceBot (talk | contribs)
Changed an Item
 
(3 intermediate revisions by 2 users not shown)
aliases / en / 0aliases / en / 0
 
Linear-size approximations to the vietoris-rips filtration
description / endescription / en
scientific article
scientific article; zbMATH DE number 6327775
Property / title
 
Linear-size approximations to the vietoris-rips filtration (English)
Property / title: Linear-size approximations to the vietoris-rips filtration (English) / rank
 
Normal rank
Property / zbMATH Open document ID
 
Property / zbMATH Open document ID: 1293.55007 / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.1145/2261250.2261286 / rank
 
Normal rank
Property / published in
 
Property / published in: Proceedings of the twenty-eighth annual symposium on Computational geometry / rank
 
Normal rank
Property / publication date
 
7 August 2014
Timestamp+2014-08-07T00:00:00Z
Timezone+00:00
CalendarGregorian
Precision1 day
Before0
After0
Property / publication date: 7 August 2014 / rank
 
Normal rank
Property / zbMATH DE Number
 
Property / zbMATH DE Number: 6327775 / rank
 
Normal rank
Property / zbMATH Keywords
 
doubling dimension
Property / zbMATH Keywords: doubling dimension / rank
 
Normal rank
Property / zbMATH Keywords
 
metric spanners
Property / zbMATH Keywords: metric spanners / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2032072254 / rank
 
Normal rank
Property / arXiv ID
 
Property / arXiv ID: 1203.6786 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Efficient data structure for representing and simplifying simplicial complexes in high dimensions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Manifold reconstruction in arbitrary dimensions using witness complexes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Topology and data / rank
 
Normal rank
Property / cites work
 
Property / cites work: Zigzag persistence / rank
 
Normal rank
Property / cites work
 
Property / cites work: Zigzag persistent homology and real-valued functions / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the local behavior of spaces of natural images / rank
 
Normal rank
Property / cites work
 
Property / cites work: Proximity of persistence modules and their diagrams / rank
 
Normal rank
Property / cites work
 
Property / cites work: Geometric inference for probability measures / rank
 
Normal rank
Property / cites work
 
Property / cites work: Towards persistence-based reconstruction in euclidean spaces / rank
 
Normal rank
Property / cites work
 
Property / cites work: Nearest neighbor queries in metric spaces / rank
 
Normal rank
Property / cites work
 
Property / cites work: Building triangulations using ε-nets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Stability of persistence diagrams / rank
 
Normal rank
Property / cites work
 
Property / cites work: Searching dynamic point sets in spaces with bounded doubling dimension / rank
 
Normal rank
Property / cites work
 
Property / cites work: Coverage in sensor networks via persistent homology / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5450061 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3655278 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Topological persistence and simplification / rank
 
Normal rank
Property / cites work
 
Property / cites work: Deformable spanners and applications / rank
 
Normal rank
Property / cites work
 
Property / cites work: An Optimal Dynamic Spanner for Doubling Metric Spaces / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q2934702 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fast Construction of Nets in Low-Dimensional Metrics and Their Applications / rank
 
Normal rank
Property / cites work
 
Property / cites work: Topological inference via meshing / rank
 
Normal rank
Property / cites work
 
Property / cites work: Zigzag persistent homology in matrix multiplication time / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3827224 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Geometric Spanner Networks / rank
 
Normal rank
Property / cites work
 
Property / cites work: The tidy set / rank
 
Normal rank
Property / cites work
 
Property / cites work: Computing persistent homology / rank
 
Normal rank

Latest revision as of 16:56, 6 July 2024

scientific article; zbMATH DE number 6327775
  • Linear-size approximations to the vietoris-rips filtration
Language Label Description Also known as
English
Linear-size approximations to the Vietoris-Rips filtration
scientific article; zbMATH DE number 6327775
  • Linear-size approximations to the vietoris-rips filtration

Statements

Linear-size approximations to the Vietoris-Rips filtration (English)
0 references
Linear-size approximations to the vietoris-rips filtration (English)
0 references
0 references
5 August 2013
0 references
7 August 2014
0 references
One of the major challenges of Computational Topology is to extract --- or should we say ``to guess''? --- the topology of an object (a subspace of a metric space, say) out of a cloud \(P\) of \(n\) sample points. One tool to this goal is the Vietoris-Rips complex \({\mathcal R}_\alpha\): Its simplices are the sets of points of \(P\) with mutual distance bounded by a fixed value \(\alpha\). Persistent Homology comes into play by varying \(\alpha\): This produces the Vietoris-Rips filtration \({\mathcal R}\) and, as usual, homology classes with longer life are assumed to be meaningful [\textit{G. Carlsson}, Bull. Am. Math. Soc., New Ser. 46, No. 2, 255--308 (2009; Zbl 1172.62002)]. Denser clouds should obviously give better information on the sampled object; still, they produce simplices of high dimension and in great numbers even with very simple objects. This paper offers a clever shortcut: A simple modification of the distance produces an alternative Vietoris-Rips filtration \(\hat{\mathcal R}\) which is proved to be arbitrarily close to the original one. The modified distance makes use of a weight function of \(\alpha\) defined for each point \(p\) of \(P\) and dependent on a deletion time \(t_p\). Deletion time is determined by organizing \(P\) as a net-tree [\textit{S. Har-Peled} and \textit{M. Mendel}, SIAM J. Comput. 35, No. 5, 1148--1184 (2006; Zbl 1100.68014)] and its use, besides in the definition of the weight, is that a point \(p\) is ignored, when \(\alpha\) exceeds \(t_p\), in the construction of a new zigzag Vietoris-Rips filtration; this is then proved to produce the same persistence diagrams as \(\hat{\mathcal R}\), but with a huge saving of simplices (\(O(n)\)).
0 references
0 references
persistent homology
0 references
Vietoris-Rips filtration
0 references
net-trees
0 references
doubling dimension
0 references
metric spanners
0 references

Identifiers

0 references
0 references
0 references
0 references
0 references
0 references
0 references