On the Structure of Straight Skeletons
Kira Vyatkina · 2008
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 M1, ..., Mkof Sc(G). We show that each Miis a pruned medial axis for a certain convex polygon Qiclosely related to G, and give an optimal algorithm for computation of all those polygons, for 1 les i les k. Here "pruned" means that Mican be obtained from the medial axis M(Qi) for Qiby appropriately trimming some (if any) edges of M(Qi) incident to the leaves of the latter.