Recognizing straight skeletons and Voronoi diagrams and reconstructing their input
2013 10th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2013)
Biedl, Therese
Held, Martin
Huber, Stefan
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.
IEEE
2013
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
http://purl.org/coar/resource_type/c_5794
https://research-explorer.app.ist.ac.at/record/2209
Biedl T, Held M, Huber S. Recognizing straight skeletons and Voronoi diagrams and reconstructing their input. In: IEEE; 2013:37-46. doi:<a href="https://doi.org/10.1109/ISVD.2013.11">10.1109/ISVD.2013.11</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1109/ISVD.2013.11
info:eu-repo/semantics/closedAccess