Graphics Reference
In-Depth Information
Table 3.1
The evolution of the
distance
attributes in Dijkstra's algorithm when applied to the
graph of Figure 3.30
v
i
distance for i
=
iteration
V
T
1
2
3
4
5
6
1
{
v
2
,
v
3
,
v
4
,
v
5
,
v
6
}
{
v
1
}
0
6
+∞
1
3
+∞
2
{
v
2
,
v
3
,
v
5
,
v
6
}
{
v
1
,
v
4
}
6
6
2
+∞
3
{
v
2
,
v
3
,
v
6
}
{
v
1
,
v
4
,
v
5
}
6
6
3
4
{
v
2
,
v
3
}
{
v
1
,
v
4
,
v
5
,
v
6
}
4
6
5
{
v
3
}
{
v
1
,
v
4
,
v
5
,
v
6
,
v
2
}
5
6
{}
{
v
1
,
v
4
,
v
5
,
v
6
,
v
2
,
v
3
}
In this example
v
s
=
v
1
and
v
t
=
v
2
. At each iteration, the distance of the vertex
u
∈
V
,
such that
∀
v
∈
V
:
u
.distance
≤
v
.distance is marked in bold in the table. This highlighted distance value indicates
that the associated vertex is transferred from
V
to
T
in that iteration. After 5 iterations the
v
t
=
v
2
condition is reached, and continuing for one iteration more the lengths of the shortest paths for all
vertices in the graph are computed.
3.
Derive the relation 3.6
n
, compute the geodesic path between them.
4.
Given two points
p
and
q
in
R
5.
Derive the relation 3.7 and the formula of geodesic path
)
6.
Write a pseudo-algorithm of the geodesic distance between two curves represented by
q
i
α
ψ
(
τ
,
i
=
1
,
2
7.
Given the edge-weighted directed graph of Figure 3.30, compute the Dijkstra's shortest
path between
v
1
and
v
2
. The growth of the set
T
, the corresponding variation of the set
V
,
and the subsequent values of the
distance
attributes of the vertices in the graph have
been listed in Table 3.1.
8.
Modify the description of Dijkstra's algorithm of Figure 3.28 in order to find the shortest
path itself instead of merely the length of the shortest path.
Suggestion: Pay special
attention to the data structure for the representation of the path.
9.
Using the Equation 3.21 derive the
w
i
,
j
,
k
between the two 3D voxels illustrated on the left
of Figure 3.33.
10.
Using Equation 3.24 and the relationship between 3D voxels in the basic arrangements,
compute the relationships between the entities A and B of Figure 3.36.
10
A
=
a
n
a
n
n
=1
4
B
=
b
m
b
m
m
=1
Figure 3.36
Two extended 3D entities comprising, respectively, 10 voxels (
A
) and 4 voxels (
B
)
