Realizability of Planar Straight-Line Graphs as Straight Skeletons
Presented by Stefan HUBER
Type: Oral presentation
Track: Discrete and Computational Geometry
The straight skeleton is a skeleton structure similar to the (generalized) Voronoi diagram. Since their introduction to computational geometry by Aichholzer et al. two decades ago, straight skeletons turned out to be a useful tool for a large number of applications in different areas of science and industry. The straight skeleton S(H) of a planar straight-line graph (PSLG) H consists of straight-line segments only. Hence, S(H) can itself be interpreted as a PSLG (with some edges forming rays to infinity). Different algorithms and implementations were presented to compute S(H) for a PSLG H. In this talk we will investigate the reverse question of computing S(H): Is a given PSLG G realizable as the straight skeleton S(H) of a PSLG H? In other words, find H such that S(H) = G. In joint work with Therese Biedl and Martin Held, we developed a method that reduces the problem of finding a suitable H to finding a line that intersects a set of convex polygons. We can find these polygons and all such lines in O(n log n) time, where n denotes the number of edges of G. It turns out that the same technique can also be used to find a suitable set of points whose Voronoi diagram realizes a given PSLG G. Thereby, we complete a partial solution for the problem Voronoi-realizability provided by Ash and Broker in 1985.