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 / 0 | aliases / en / 0 | ||||||||||||||
Linear-size approximations to the vietoris-rips filtration | |||||||||||||||
description / en | description / 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
| |||||||||||||||
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 |
|
Statements
Linear-size approximations to the Vietoris-Rips filtration (English)
0 references
Linear-size approximations to the vietoris-rips filtration (English)
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
persistent homology
0 references
Vietoris-Rips filtration
0 references
net-trees
0 references
doubling dimension
0 references
metric spanners
0 references
0 references