Name
Abstract | ||
|---|---|---|
We show how to divide the edge graph of a Voronoi diagram into a tree that corresponds to the medial axis of an (augmented) planar domain. Division into base cases is then possible, which, in the bottom-up phase, can be merged by trivial concatenation. The resulting construction algorithm--similar to Delaunay triangulation methods--is not bisector-based and merely computes dual links between the sites, its atomic steps being inclusion tests for sites in circles. This guarantees computational simplicity and numerical stability. Moreover, no part of the Voronoi diagram, once constructed, has to be discarded again. The algorithm works for polygonal and curved objects as sites and, in particular, for circular arcs which allows its extension to general free-form objects by Voronoi diagram preserving and data saving biarc approximations. The algorithm is randomized, with expected runtime O(n log n) under certain assumptions on the input data. Experiments substantiate an efficient behavior even when these assumptions are not met. Applications to offset computations and motion planning for general objects are described. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.comgeo.2010.04.004 | Computational Geometry: Theory and Applications |
Keywords | DocType | Volume |
divide-and-conquer,bottom-up phase,input data,voronoi diagram,n log n,trimmed offset,atomic step,motion planning,base case,certain assumption,medial axis,algorithm work,resulting construction algorithm,voronoi diagrams revisited,biarc approximation,general object,general free-form object,bottom up,motion,top down,delaunay triangulation,theory,divide and conquer,algorithms,numerical stability | Conference | 43 |
Issue | ISSN | Citations |
8 | Computational Geometry: Theory and Applications | 13 |
PageRank | References | Authors |
0.60 | 27 | 7 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oswin Aichholzer | 1 | 852 | 96.04 |
| Wolfgang Aigner | 2 | 25 | 2.43 |
| Franz Aurenhammer | 3 | 2060 | 202.90 |
| Thomas Hackl | 4 | 138 | 22.95 |
| Bert Jüttler | 5 | 1148 | 96.12 |
| Elisabeth Pilgerstorfer | 6 | 13 | 0.60 |
| Margot Rabl | 7 | 13 | 0.94 |