Recognizing straight skeletons and Voronoi diagrams and reconstructing their input Conference Paper


Author(s): Biedl, Therese; Held, Martin; Huber, Stefan
Title: Recognizing straight skeletons and Voronoi diagrams and reconstructing their input
Title Series: 2013 10th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2013)
Affiliation IST Austria
Abstract: 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.
Conference Title: ISVD: Voronoi Diagrams in Science and Engineering
Conference Dates: July 8-10, 2013
Conference Location: Saint Petersburg, Russia
ISBN: 9781479905485
Publisher: IEEE  
Date Published: 2013-12-01
Start Page: 37
End Page: 46
DOI: 10.1109/ISVD.2013.11
Open access: no
IST Austria Authors
  1. Stefan Huber
    11 Huber
Related IST Austria Work