Graphics Reference
In-Depth Information
9. REEB GRAPHS
eorem 9.3
If
n3
the degree of vertices
0
i
of index
1
(or
n1
) is
2
or
3
. If
nD2
the degree of
vertices
0
i
of index
1
is
2
,
3
, or
4
. e degree of vertices
0
i
of index different from
0
,
1
,
n1
, or
n
is
2
.
In other words, the theorem
9.2
states that leaf nodes of
K
can be either maxima or minima
of
f
, while from the theorem
9.3
we can deduce that, for
2
-manifolds that can be embedded in
R
3
, the degree of vertices representing saddles is always
3
(see section
8.1
).
Several variations/approximations of the Reeb graph exist; among the others we mention
the Multiresolution Reeb Graph (MRG) [
102
], the Extended Reeb Graph (ERG) [
6
], the aug-
mented Multiresolution Reeb Graph (aMRG) [
202
], the Discrete Reeb Graph (DRG) [
211
].
Strictly related to Reeb graphs are
contour trees
. Contour trees are a special case of Reeb
graphs, in which the shape (i.e., the domain of the function) is simply connected and with a
single border element. Contour trees were introduced for practical issues, mainly as a tool for
topographic analysis. Indeed, the evolution of contour lines on a surface explicitly represents hills
and dales with their elevation-based adjacency relationships. erefore, contour trees are an effi-
cient data structure to store containment relationships among contours in contour maps, typically
representing terrain elevations [
30
]. Several variations of contour trees have been proposed in the
literature, as for example the
volume skeleton tree
by Takahashi et al. [
192
]. e contour tree may
also be augmented with further information on all topological changes of the level sets by adding
nodes that correspond to critical values where not the number but the topology of the contours
changes. Examples are the
contour topology tree
[
46
], the
criticality tree
[
52
], and the
topographic
change tree
[
87
].
Computational complexity
Historically, the first algorithm was proposed by Shinagawa and
Kunii in 1991. It ran over height functions defined on a triangulated 2-manifold [
181
] and had
a computational complexity of
O.n
2
/
, where
n
is the number of triangles in the triangulation.
e algorithm proposed by Cole-Mclaughlin et al. [
48
] showed how to compute the graph in
O.n
log
n/
operations by maintaining the level sets using dynamically balanced search trees fol-
lowing the algorithm for contour trees in all dimensions by Carr et al [
40
]. However, in higher
dimensions, the presence of loops in the Reeb graph implies that its decomposition into a join
and split tree, which was crucial for the efficiency of the algorithm by Carr et al. [
40
] and Cole-
Mclaughlin et al. [
48
], may not exist and, therefore the algorithm proposed in [
48
] does not
extend to
3
-manifolds.
Pascucci et al. [
159
] proposed an online algorithm that constructs the Reeb graph for
streaming data. eir algorithm takes advantage of the coherency in the input to construct the
Reeb graph for simplicial complexes of arbitrary dimension. ough the algorithm performs well
in practice, it has a worst case time complexity of
O.nm/
, where
n
is the number of vertices
and
m
is the number of triangles in the complex. Tierny et al. further improved the complexity
of computing a Reeb graph of
3D
manifolds with boundary embedded in
R
3
using cuts to re-
Search WWH ::
Custom Search