Computational Geometry in the Human Brain - Discrete and Computational Geometry and Graphs - page 155

The third type of event is that a forefront cycle of length 3 disappears, as
showninFig. 13 . In this case three active edges become fixed, three roof plates
become completely bounded by fixed edges, and no new edges are generated.
On the basis of these observations, we can make Algorithm 1 robust by
modifying Step 5 in the following way.
Algorithm 2 (Robust construction of straight skeleton).
Step 5 of Algorithm 1 is replaced with the following step, and the remainder
is the same as Algorithm 1.
5'. Repeat the following until E and S are empty.
5.1' Find a pair ( e, s ) of an active roof edge e and a nonneighboring roof plate
s incident to the same forefront cycle, such that their intersection is the
lowest.
5.2' If the event is of type 1, move e and its neighboring edge from E to E ,
generate a new active edge , and reconnect the forefront cycle, as shown
in Fig. 11 .Movefrom S to S the roof plate t ha t has become fixed.
5.3' If the event is of type 2, move e from E to E , generate two new active
edges, and partition the forefront cycle into two, as shown in Fig. 12 .
5.4' If the event is of type 3, move the three edges (including e )from E to
E , and change the associated t hree active edges to fixed edges, as shown
in Fig. 13 .Movefrom S to S the three roof plates that have become
fixed.
Note that this algorithm does not encounter the topological inconsistency shown
in Fig. 9 . Indeed, at the initial stage (Fig. 9 (a)), a forefront cycle of length 7 is
generated, and in the first event shown in Fig. 9 (b), which is a type-2 event, the
forefront cycle is partitioned into two forefront cycles of length 4. Hence, the
situation shown in Fig. 9 (c) does not arise because the associated roof edge and
the roof plate are incident to different forefront cycles, and hence this pair is not
included in the event candidates in Algorithm 2.
In Algorithm 2, we restrict the event search to each forefront cycle. In this
search, we cannot necessarily find the correct event (i.e., the lowest intersection)
because of numerical errors. However, whatever pair of a roof edge and a roof
plate is chosen as the next event, no topological inconsistency will arise because
the chosen pair will be of type 1, 2, or 3, and thus the topological change of the
forefront cycle will be well defined.
In other words, the basic structure of Algorithm 2 allows the topological
change of the graph structure of the forefront cycles, and numerical computations
are used only to choose the most promising pair of a roof edge and a roof plate.
Once this pair is chosen, the algorithm persists in the belief that it gives the
lowest intersection and changes the forefront cycles by Steps 5.2', 5.3', or 5.4' of
Algorithm 2, depending on the type of the event. Thus we obtain the following
theorem.