Reconstructing polygons from embedded straight skeletons Conference Paper


Author(s): Biedl, Therese; Held, Martin; Huber, Stefan
Title: Reconstructing polygons from embedded straight skeletons
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. 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 17-20, 2013
Conference Location: Braunschweig, Germany
Publisher: TU Dortmund  
Date Published: 2013-03-01
Start Page: 95
End Page: 98
URL:
Open access: no
IST Austria Authors
  1. Stefan Huber
    11 Huber
Related IST Austria Work