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

Theorem 1. Algorithm 2 terminates in finite time and produces a planar graph
as output, no matter whether the pair ( e, s ) chosen in Step 5.1' gives the true
lowest intersection or not.

Proof. Once a pair ( e, s ) is chosen in Step 5.1', the associated event is of type 1,
type 2, or type 3, and hence the planar graph consisting of the original polygon
edges, active edges, fixed edges, forefront cycle edge, and their terminal vertices
is changed by Steps 5.2', 5.3', or 5.4', all of which maintain planarity. Thus, it
suces to show the finiteness of the procedure. Assume that the input polygon P
has n edges. Initially, the total number of edges on the forefront cycle is n . This
number decreases by one in a type 1 event and by three in a type 3 event. In a
type 2 event, the total number of edges on the forefront cycles increases by one,
but both of the forefront cycles generated by the partition are smaller by at least
two than the forefront cycle before the partition. Hence, Step 5.3' is repeated
only a finite number of times, and thus the total number of the forefront cycles
eventually vanishes.

Theorem 2. Algorithm 2 runs in O( n 2 log n ) time for an n -gon P .

Proof. Steps 1, 2, and 3 are carried out in time O( n ), and Step 4 is carried
out in time O(1). Step 5' can be performed in the following manner. Initially
there are n active edges and n active roof plates. Hence there are n ( n

2) pairs
of roof edges and nonneighboring roof plates. We store them in a heap with
the y -coordinates of the points of intersection as the keys [ 1 ]. We can construct
the heap in O( n 2 log n ) time. Deletion of the lowest pair ( e, s ) from the heap
in Step 5.1' requires O(log n ) time. In Steps 5.2' and 5.3', new active edges are
generated. As soon as a new active edge e is generated, we compute the point of
intersection with each of the nonneighboring roof plates on the same forefront
cycle, and add the pair ( e, s ) to the heap. Adding a pair to the heap requires
O(log n ) time. Because there are O( n ) roof plates on the same forefront cycle,
we can add all the pairs with e totheheapinO( n log n ) time. Hence, Steps 5.2'
and 5.3' can be completed in O( n log n ) time. Step 5.4' can be completed in O(1)
time. Note that the straight skeleton is a planar graph with n connected regions
(corresponding to the n edges of the input polygon) embedded in the plane, and
the degree of any vertex is at least three. Hence, the total number of vertices,
edges, and connected regions is of O( n ). This means that Steps 5.1 to 5.4 are
repeated O( n ) times. Therefore, Algorithm 2 runs in O( n 2 log n ) time.

−

Figure 14 shows an example of a straight skeleton. The input polygon in this
figure has 300 vertices. This polygon was generated by inserting a number of
vertices into the edges of a 16-gon and then perturbing their locations with small
random numbers. This polygon is not degenerate, and hence the construction of
the straight skeleton is not dicult.
Figure 15 shows the output of our algorithm for a regular 30-gon. This is
highly degenerate because, if there are no numerical errors, all 30 of the roof
edges will meet at the center. In this experiment, the coordinates of the vertices
were represented by single-precision floating-point numbers, and the numerical