Measuring and computing natural generators for homology groups

被引：28

作者：

Chen, Chao ^{[1
]}

Freedman, Daniel ^{[1
]}

机构：

[1] Rensselaer Polytech Inst, Troy, NY 12180 USA

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2010年 / 43卷 / 02期

关键词：

Computational topology; Computational geometry; Homology; Persistent homology; Homology basis; Stability; Finite field linear algebra; PERSISTENCE; TOPOLOGY;

D O I：

10.1016/j.comgeo.2009.06.004

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We develop a method for measuring homology classes. This involves two problems. First, we define the size of a homology class, using ideas from relative homology. Second, we define an optimal basis of a homology group to be the basis whose elements' size have the minimal sum. We provide a greedy algorithm to compute the optimal basis and measure classes in it. The algorithm runs in O (beta log(2) n) time, where n is the size of the simplicial complex and beta is the Betti number of the homology group. Finally, we prove the stability of our result. The algorithm can be adapted to measure any given class. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：169 / 181

页数：13

共 24 条

[1] Extreme elevation on a 2-manifold [J].

Agarwal, Pankaj K. ;

Edelsbrunner, Herbert ;

Harer, John ;

Wang, Yusu .

DISCRETE & COMPUTATIONAL GEOMETRY, 2006, 36 (04) :553-572

[2]

Carlsson G., 2005, International Journal of Shape Modeling, V11, P149, DOI [DOI 10.1145/1057432.1057449, 10.1142/S0218654305000761, DOI 10.1142/S0218654305000761]

[3]

CARLSSON G, 2005, FIELDS OTT WORKSH GE

[4]

CARLSSON G, 2007, P 23 ACM S COMP GEOM, P184, DOI DOI 10.1145/1247069.1247105

[5]

Carner C, 2005, IEEE VISUALIZATION 2005, PROCEEDINGS, P543

[6]

CHEN C, 2009, HARDNESS RESULTS HOM

[7]

Chen C, 2008, STACS 2008: PROCEEDINGS OF THE 25TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, P169

[8]

Cohen-Steiner D., 2006, Proceedings of the Twenty-Second Annual Symposium on Computational Geometry (SCG'06), P119, DOI 10.1145/1137856.1137877

[9]

Cohen-Steiner D, 2009, PROCEEDINGS OF THE TWENTIETH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P1011

[10] Extending Persistence Using Poincare and Lefschetz Duality [J].

Cohen-Steiner, David ;

Edelsbrunner, Herbert ;

Harer, John .

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS, 2009, 9 (01) :79-103

← 1 2 3 →