--- res: bibo_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.\r\n@eng" bibo_authorlist: - foaf_Person: foaf_givenName: Therese foaf_name: Biedl, Therese foaf_surname: Biedl - foaf_Person: foaf_givenName: Martin foaf_name: Held, Martin foaf_surname: Held - foaf_Person: foaf_givenName: Stefan foaf_name: Huber, Stefan foaf_surname: Huber foaf_workInfoHomepage: http://www.librecat.org/personId=4700A070-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0002-8871-5814 bibo_doi: 10.1109/ISVD.2013.11 dct_date: 2013^xs_gYear dct_language: eng dct_publisher: IEEE@ dct_title: Recognizing straight skeletons and Voronoi diagrams and reconstructing their input@ ...