Author(s):

Biedl, Therese; Held, Martin; Huber, Stefan

Title: 
Reconstructing polygons from embedded straight skeletons

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. In this paper, we ask the reverse question: Given the straight skeleton (in form of a tree with a drawing in the plane, but with the exact position of the leaves unspecified), can we reconstruct the polygon? We show that in most cases there exists at most one polygon; in the remaining case there is an infinite number of polygons determined by one angle that can range in an interval. We can find this (set of) polygon(s) in linear time in the Real RAM computer model.

Conference Title:

EuroCG: European Workshop on Computational Geometry

Conference Dates:

March 1720, 2013

Conference Location:

Braunschweig, Germany

Publisher:

TU Dortmund

Date Published:

20130301

Start Page: 
95

End Page:

98

URL: 

Open access: 
no 