A straight skeleton is a well-known geometric structure, and several algorithms exist to construct the straight skeleton for a given polygon or planar straight-line graph. In this paper, we ask the reverse question: Given the straight skeleton (in form of a planar straight-line graph, with some rays to infinity), can we reconstruct a planar straight-line graph for which this was the straight skeleton? We show how to reduce this problem to the problem of finding a line that intersects a set of convex polygons. We can find these convex polygons and all such lines in $O(nlog n)$ time in the Real RAM computer model, where $n$ denotes the number of edges of the input graph. We also explain how our approach can be used for recognizing Voronoi diagrams of points, thereby completing a partial solution provided by Ash and Bolker in 1985.
展开▼
机译：直线骨架是众所周知的几何结构，并且存在多种算法来构造给定多边形或平面直线图的直线骨架。在本文中，我们提出一个相反的问题：给定笔直的骨架（以平面直线图的形式，有一些射线到无穷远），我们可以重建一个平面直线图吗？我们展示了如何将这个问题简化为找到与一组凸多边形相交的线的问题。在Real RAM计算机模型中，我们可以在$ O（nlog n）$时间内找到这些凸多边形和所有此类线，其中$ n $表示输入图的边数。我们还将解释如何将我们的方法用于识别点的Voronoi图，从而完成Ash和Bolker在1985年提供的部分解决方案。
展开▼
