AN INCREMENTAL ALGORITHM FOR BETTI NUMBERS OF SIMPLICIAL COMPLEXES ON THE 3-SPHERE

被引：111

作者：

DELFINADO, CJA ^{[1
]}

EDELSBRUNNER, H ^{[1
]}

机构：

[1] UNIV ILLINOIS,DEPT COMP SCI,URBANA,IL 61801

来源：

COMPUTER AIDED GEOMETRIC DESIGN | 1995年 / 12卷 / 07期

基金：

美国国家科学基金会;

关键词：

SOLID MODELING; GEOMETRIC ALGORITHMS; GRAPH ALGORITHMS; ALGEBRAIC TOPOLOGY; SIMPLICIAL COMPLEXES; FILTRATIONS; ALPHA SHAPES; HOMOLOGY GROUPS; BETTI NUMBERS; UNION-FIND; DEPTH-FIRST SEARCH;

D O I：

10.1016/0167-8396(95)00016-Y

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

A general and direct method for computing the Betti numbers of a finite simplicial complex in Bd is given. This method is complete for d less than or equal to 3, where versions of this method run in time O(n alpha(n)) and O(n), n the number of simplices. An implementation of the algorithm is applied to alpha shapes, which is a novel geometric modeling tool.

引用

页码：771 / 784

页数：14

共 15 条

[1]

Alexandroff P, 1935, TOPOLOGIE, VI, P79

[2]

BERN M, 1993, 9TH P ANN ACM S COMP, P281

[3]

DELFINADO CJA, 1993, 9TH P ANN S COMP GEO, P232

[4]

Donald BR, 1991, 32 ANN S FDN COMP SC, P650

[5] 3-DIMENSIONAL ALPHA-SHAPES [J].

EDELSBRUNNER, H ;

MUCKE, EP .

ACM TRANSACTIONS ON GRAPHICS, 1994, 13 (01) :43-72

[6]

EDELSBRUNNER H, 1983, IEEE T INFORM THEORY, V29, P551, DOI 10.1109/TIT.1983.1056714

[7]

Edelsbrunner H, 1987, ALGORITHMS COMBINATO

[8]

GIBLIN P, 1981, GRAPHS SURFACES HOMO

[9]

Hoffmann C. M., 1989, GEOMETRIC SOLID MODE

[10] POLYNOMIAL ALGORITHMS FOR COMPUTING THE SMITH AND HERMITE NORMAL FORMS OF AN INTEGER MATRIX [J].

KANNAN, R ;

BACHEM, A .

SIAM JOURNAL ON COMPUTING, 1979, 8 (04) :499-507

← 1 2 →