Zigzag Persistent Homology and Real-valued Functions

被引：95

作者：

Carlsson, Gunnar ^{[1
]}

de Silva, Vin ^{[1
]}

Morozov, Dmitriy ^{[1
]}

机构：

[1] Stanford Univ, Dept Math, Stanford, CA 94305 USA

来源：

PROCEEDINGS OF THE TWENTY-FIFTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY (SCG'09) | 2009年

关键词：

Zigzag persistent homology; Mayer-Vietoris pyramid; levelset zigzag; extended persistence; algorithms; STABILITY;

D O I：

10.1145/1542362.1542408

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We study the problem of computing zigzag persistence of a sequence of homology groups and study a particular sequence derived from the levelsets of a real-valued function on a topological space. The result is a local, symmetric interval descriptor of the function. Our structural results establish a connection between the zigzag pairs in this sequence and extended persistence, and in the process resolve an open question associated with the latter. Our algorithmic results not only provide a way to compute zigzag persistence for any sequence of homology groups, but combined with our structural results give a novel algorithm for computing extended persistence. This algorithm is easily parallelizable and uses (asymptotically) less memory.

引用

页码：247 / 256

页数：10

共 16 条

[1] Abdi H., 2007, ENCY RES METHODS SOC, P598, DOI DOI 10.4135/9781412952644
[2] CARLSSON G, 2008, TOPOLOGY DATA
[3] CARLSSON G, 2008, ARXIV08120197V1
[4] CHAZAL F, 2009, P ANN S COM IN PRESS
[5] Chazal F, 2009, PROCEEDINGS OF THE TWENTIETH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P1021
[6] Cohen-Steiner D., 2006, Proceedings of the Twenty-Second Annual Symposium on Computational Geometry (SCG'06), P119, DOI 10.1145/1137856.1137877
[7] Stability of persistence diagrams
Cohen-Steiner, David
Edelsbrunner, Herbert
Harer, John
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 2007, 37 (01) : 103 - 120
[8] Cohen-Steiner D, 2009, PROCEEDINGS OF THE TWENTIETH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P1011
[9] COHENSTEINER D, 2009, FDN COMPUTATIONAL MA, V8, P79
[10] Stability of critical points with interval persistence
Dey, Tamal K.
Wenger, Rephael
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 2007, 38 (03) : 479 - 512

← 1 2 →