Loops in Reeb graphs of 2-manifolds

被引：67

作者：

Cole-McLaughlin, K ^{[1
]}

Edelsbrunner, H

Harer, J

Natarajan, V

Pascucci, V

机构：

[1] Lawrence Livermore Natl Lab, Ctr Appl Sci Comp, Livermore, CA 94551 USA

[2] Duke Univ, Dept Math, Durham, NC 27708 USA

[3] Duke Univ, Dept Comp Sci, Durham, NC 27708 USA

[4] Raindrop Geomag, Res Triangle Pk, NC 27709 USA

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 2004年 / 32卷 / 02期

关键词：

D O I：

10.1007/s00454-004-1122-6

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Given a Morse function f over a 2-manifold with or without boundary, the Reeb graph is obtained by contracting the connected components of the level sets to points. We prove tight upper and lower bounds on the number of loops in the Reeb graph that depend on the genus, the number of boundary components, and whether or not the 2-manifold is orientable. We also give an algorithm that constructs the Reeb graph in time O(n log n), where n is the number of edges in the triangulation used to represent the 2-manifold and the Morse function.

引用

页码：231 / 244

页数：14

共 18 条

[1]

Alexandrov P. S., 1998, COMBINATORIAL TOPOLO

[2] The contour spectrum [J].

Bajaj, CL ;

Pascucci, V ;

Schikore, DR .

VISUALIZATION '97 - PROCEEDINGS, 1997, :167-+

[3] Computing contour trees in all dimensions [J].

Carr, H ;

Snoeyink, J ;

Axen, U .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2003, 24 (02) :75-94

[4]

Cormen T. H., 1994, INTRO ALGORITHMS

[5] Hierarchical morse-smale complexes for piecewise linear 2-manifolds [J].

Edelsbrunner, H ;

Harer, J ;

Zomorodian, A .

DISCRETE & COMPUTATIONAL GEOMETRY, 2003, 30 (01) :87-107

[6]

Fomenko A.T., 1997, TOPOLOGICAL METHODS

[7]

Goresky M, 1988, STRATIFIED MORSE THE

[8]

Hilaga M, 2001, COMP GRAPH, P203, DOI 10.1145/383259.383282

[9]

Massey W. S., 1967, ALGEBRAIC TOPOLOGY I

[10] A LOWER BOUND ON THE COMPLEXITY OF THE UNION-SPLIT-FIND PROBLEM [J].

MEHLHORN, K ;

NAHER, S ;

ALT, H .

SIAM JOURNAL ON COMPUTING, 1988, 17 (06) :1093-1102

← 1 2 →