Name
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(n\log 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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/ISVD.2013.11 | ISVD |
Keywords | Field | DocType |
partial solution,well-known geometric structure,real ram computer model,convex polygon,reverse question,voronoi diagrams,recognizing straight skeletons,log n,planar straight-line graph,voronoi diagram,input graph,straight skeleton,solids,computational geometry,reconstruction,computational complexity,computational modeling,skeleton | Geometric graph theory,Discrete mathematics,Combinatorics,Polygon,Beta skeleton,Planar straight-line graph,Straight skeleton,Polyhedral graph,Voronoi diagram,Mathematics,Planar graph | Conference |
Citations | PageRank | References |
2 | 0.40 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Therese Biedl | 1 | 902 | 106.36 |
| Martin Held | 2 | 700 | 62.94 |
| Stefan Huber | 3 | 24 | 3.38 |