Graphics Reference
In-Depth Information
7. ALGEBRAIC TOPOLOGY AND TOPOLOGY INVARIANTS
Specifically, an element of
H
q
.K/
is an equivalence class, called
homology class
, of homologous
q
-
cycles, i.e., cycles whose difference is a boundary. e homology
H
.K/
is a topological invariant
of
K
; it is indeed an invariant of homotopy type.
e rank of
H
q
.K/
is called the
q
-
th
Betti number
of
K
, and it is a measurement of the
number of different holes in the space
K
. As an example, for three-dimensional data the three
Betti numbers
0
,
1
and
2
count the number of connected components, tunnels and voids,
respectively. e Betti numbers can be used to define a well-known topological invariant, the
Euler characteristic
:
.K/D
P
n
iD0
.1/
i
i
.K/
. rough the Euler characteristics it is possible to
provide an alternative definition of the genus of a closed surface (cf. the definition in chapter
3
)
through the relationship
D22g
, where
g
is the genus. For surfaces with
b
boundary com-
ponents, the relation becomes
D22gb
.
A
simplicial map
f
between two simplicial complexes
K
and
L
(i.e., a function from the
set of vertices of
K
to the set of vertices of
L
such that the image of any simplex in
K
is a simplex
in
L
) induces uniquely a set
H
.f /
of homomorphisms between the homology groups:
H
q
.f /WH
q
.K/!H
q
.L/
for each degree
q
. e maps
H
q
.f /
satisfy two elementary properties: (i) the identity map
id
K
W
K!K
induces the identity map on homology; and (ii) the composition
gf
of two maps
corresponds to the composition
H
q
.gf /DH
q
.g/H
q
.f /
of the induced homomorphisms.
7.2.1 CONCEPTS IN ACTION
Betti numbers, homology groups and generators
In case of a triangle mesh
T
the Euler charac-
teristics reduces to
.T/DVECF
, where
V
,
E
and
T
represent respectively the number of
vertices (
0
-simplices), edges (
1
-simplices) and faces (
2
-simplices) of the triangulation
T
. ere-
fore, its computation is straightforward. A recent example of application of Euler characteristics
applied to the analysis and filtering of the seafloor has been proposed in [
77
].
More in general, there is a classical algorithm to compute the homology groups of an arbi-
trary simplicial complex (see Munkres [
149
]), based on reducing certain matrices to a canonical
form, called
Smith normal form
. Unfortunately, the reduction of a matrix to its Smith normal
form has a worst-case upper bound that is computationally prohibitive. To avoid the bottleneck
of its computation, Delfinado & Edelsbrunner [
56
] describe an algorithm that computes the Betti
numbers of a simplicial complex in
R
3
. e intuition behind such an approach is to assemble the
complex incrementally simplex by simplex, and at each step update the Betti numbers of the cur-
rent complex. e algorithm runs optimally in time and space linear in the size of the complex.
For a triangulated surface of genus
g
, with a total of
n
simplices, a set of canonical generators
of the homology groups can be computed in
O.gn/
time, which is optimal in the worst case [
204
].
Each of the
g
or
2g
canonical generators is represented by a polygonal curve whose vertices
are on the
1
-skeleton, while the other points are in the interior of a
2
-simplex. A simple, yet
computationally efficient, algorithm is to remove iteratively simplices preserving at each step the
Search WWH ::
Custom Search