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 wellknown geometric structure, and several algorithms exist to construct the straight skeleton for a given polygon or planar straightline graph. In this paper, we ask the reverse question: Given the straight skeleton (in form of a planar straightline graph, with some rays to infinity), can we reconstruct a planar straightline 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 810, 2013

Conference Location:

Saint Petersburg, Russia

ISBN:

9781479905485

Publisher:

IEEE

Date Published:

20131201

Start Page: 
37

End Page:

46

DOI: 
10.1109/ISVD.2013.11

Open access: 
no 