Biomedical Engineering Reference
In-Depth Information
Increasing
values of ϕ
Figure 4.4:
Example of a binary tree for the heap sort algorithm.
A higher order version of the fast marching method can be obtained by
replacing Eq. 4.23 with
2
D
−
x
D
−
x
φ
i
,
j
+
s
x
,
−
1
s
x
,
−
2
x
2
max(
D
−
x
φ
i
,
j
+
s
x
,
−
1
x
D
−
x
D
−
x
D
−
x
φ
i
,
j
,
6
2
D
+
x
D
+
x
φ
i
,
j
−
s
x
,
1
s
x
,
2
x
2
−
D
+
x
φ
i
,
j
−
s
x
,
1
x
D
+
x
D
+
x
D
+
x
φ
i
,
j
,
0)
2
6
2
D
−
y
D
−
y
φ
i
,
j
+
s
y
,
−
1
s
y
,
−
2
y
2
+
max(
D
−
y
φ
i
,
j
+
s
y
,
−
1
y
D
−
y
D
−
y
D
−
y
φ
i
,
j
,
6
2
D
+
y
D
+
y
φ
i
,
j
−
s
y
,
1
s
y
,
2
y
2
−
D
+
y
φ
i
,
j
−
s
y
,
1
y
D
+
y
D
+
y
D
+
y
φ
i
,
j
,
0)
2
6
1
F
i
,
j
.
(4.25)
=
The fast marching method algorithm presented in [105], is first-order accurate
and can be recovered from Eq. 4.25 by taking all the switches
s
∗
,
∗
=
0. The
second-order accurate method presented in [106] can also be recovered from
Eq. 4.25 by taking all the switches
s
∗
,
±
2
=
0.
The Heap-Sort Algorithm
The heap sort algorithm employed in the fast marching method is a balanced
binary-tree structure which always maintains the smallest value of
φ
at the top.
For purposes of illustration, see Fig. 4.4. The top of the tree is indicated by the
single node at the top in Fig. 4.4. Each of the nodes connected to the top is called
the child of that node, and the top node is the parent of its children. Except for
the top node, each node has one parent, and may have zero, one, or two children
depending upon where it is in the tree.
The operations on the tree that are required for the fast marching method
are:
1. Resort the tree from one element.
