Graphics Reference
In-Depth Information
V
2
V
2
V
V
V
1
V
1
V
4
V
0
V
0
d
d
E
E
V
3
(a)
(b)
Figure 9.12
(a) Hill climbing from
V
to the most extreme vertex
E
(in direction
d
) using
adjacent vertices only.
(b) Accelerated hill climbing using additional (artificial adjacency)
information.
neighboring vertex is more extreme the current vertex is guaranteed to be an extreme
vertex. This approach is very efficient, as it explores only a small corridor of vertices
as it moves toward the extreme vertex.
Figure 9.12a illustrates the hill-climbing algorithm on a dodecahedron. Here, the
current vertex
V
has three adjacent vertices
V
0
,
V
1
, and
V
2
.
V
0
is more extreme than
V
in search direction
d
because (
V
0
−
0 and is thus made the new current
vertex. Three additional steps are taken in the same way (indicated by thick arrows)
until vertex
E
is finally reached. Because none of the neighbors of
E
are more extreme
than
E
itself,
E
must be the most extreme vertex in direction
d
, and the search stops.
For larger polyhedra, the hill climbing can be sped up by adding one or more
artificial neighbors
to the adjacency list for a vertex. By linking to vertices at a greater
distance away from the current vertex (measured in the smallest number of steps
along edges between the two vertices), the hill-climbing algorithm is likely to make
faster progress toward the most extreme vertex when moving through these artificial
vertices. A simple approach is to assign artificial neighbors randomly. More intelligent
algorithms can be employed to ensure artificial neighbors are at least some distance
k
away from the current vertex. To make sure the artificial neighbors are actually
considered during hill climbing, it is a good idea to list them first on the list of
neighboring vertices. Alternatively, a steepest descent rule can be employed: instead
of moving to the first neighboring vertex more extreme, all neighbors are examined
and the neighboring vertex most extreme is made the new current vertex. Figure 9.12b
illustrates the hill-climbing algorithm with the addition of two artificial neighbors to
the start vertex
V
and using a steepest descent rule. Now,
E
is reached in just two steps.
V
)
·
d
>
