---
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@
...