On the Structure of Straight Skeletons

For a planar straight line graph G, its straight skeleton S(G) can be partitioned into two subgraphs SC(G) and Sr(G) traced out by the convex and by the reflex vertices of the linear wavefront, respectively. By further splitting SC(G) at the nodes, at which the reflex wavefront vertices vanish, we obtain a set of connected subgraphs M₁, ..., M_k of S^c(G). We show that each M_i is a pruned medial axis for a certain convex polygon Q_i closely related to G, and give an optimal algorithm for computation of all those polygons, for 1 les i les k. Here "pruned" means that M_i can be obtained from the medial axis M(Q_i) for Q_i by appropriately trimming some (if any) edges of M(Q_i) incident to the leaves of the latter.