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 [J].

Cohen-Steiner, David ;

Edelsbrunner, Herbert ;

Harer, John .

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 [J].

Dey, Tamal K. ;

Wenger, Rephael .

DISCRETE & COMPUTATIONAL GEOMETRY, 2007, 38 (03) :479-512

← 1 2 →