×

Divide-and-conquer for Voronoi diagrams revisited. (English) Zbl 1207.05190

Summary: 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.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Software:

VRONI
Full Text: DOI

References:

[2] Aichholzer, O.; Aigner, W.; Aurenhammer, F.; Hackl, T.; Jüttler, B.; Rabl, M., Medial axis computation for planar free-form shapes, Computer-Aided Design, 41, 5, 339-349 (2009), Special issue: Voronoi Diagrams and their Applications
[3] Aichholzer, O.; Aurenhammer, F.; Hackl, T.; Jüttler, B.; Oberneder, M.; Šír, Z., Computational and structural advantages of circular boundary representation, (Springer Lecture Notes in Computer Science, vol. 4619 (2007)), 374-385 · Zbl 1209.68574
[4] Alt, H.; Cheong, O.; Vigneron, A., The Voronoi diagram of curved objects, Discrete & Computational Geometry, 34, 439-453 (2005) · Zbl 1079.52014
[5] Cao, L.; Liu, J., Computation of medial axis and offset curves of curved boundaries in planar domain, Computer-Aided Design, 40, 4, 465-475 (2008)
[6] CGAL, Computational Geometry Algorithms Library · Zbl 1365.68441
[9] Chin, F. Y.L.; Snoeyink, J.; Wang, C. A., Finding the medial axis of a simple polygon in linear time, Discrete & Computational Geometry, 21, 405-420 (1999) · Zbl 0922.68128
[10] Choi, H. I.; Choi, S. W.; Moon, H. P., Mathematical theory of medial axis transform, Pacific Journal of Mathematics, 181, 57-88 (1997) · Zbl 0885.53004
[11] Elber, G.; Cohen, E.; Drake, S., MATHSM: Medial axis transform toward high speed machining of pockets, Computer-Aided Design, 37, 241-250 (2005)
[13] Fortune, S., A sweep line algorithm for Voronoi diagrams, Algorithmica, 2, 153-174 (1987) · Zbl 0642.68079
[14] Held, M., Voronoi diagrams and offset curves of curvilinear polygons, Computer-Aided Design, 30, 4, 287-300 (1998) · Zbl 1084.68914
[15] Held, M., VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments, Computational Geometry: Theory and Applications, 18, 2, 95-123 (2001) · Zbl 0976.68162
[16] Held, M.; Huber, S., Topology-oriented incremental computation of Voronoi diagrams of circular arcs and straight-line segments, Computer-Aided Design, 41, 5, 327-338 (2009), Special issue: Voronoi Diagrams and their Applications · Zbl 1206.65087
[17] Held, M.; Lukacs, G.; Andor, L., Pocket machining based on contour-parallel tool paths generated by means of proximity maps, Computer-Aided Design, 26, 3, 189-203 (1994) · Zbl 0803.68150
[19] Klein, R., Concrete and Abstract Voronoi Diagrams, Lecture Notes in Computer Science, vol. 400 (1990), Springer · Zbl 0699.68005
[20] Klein, R.; Mehlhorn, K.; Meiser, S., Randomized incremental construction of abstract Voronoi diagrams, Computational Geometry: Theory and Applications, 3, 157-184 (1993) · Zbl 0797.68153
[21] Kreyszig, E., Differential Geometry (1991), Dover: Dover New York
[22] Lee, D. T., Medial axis transformation of a planar shape, IEEE Trans. Pattern Analysis and Machine Intelligence, 4, 363-369 (1982) · Zbl 0483.68085
[23] Lee, D. T.; Drysdale, R. L.S., Generalization of Voronoi diagrams in the plane, SIAM Journal on Computing, 10, 73-87 (1981) · Zbl 0454.68083
[24] McAllister, M.; Kirkpatrick, D.; Snoeyink, J., A compact piecewise-linear Voronoi diagram for convex sites in the plane, Discrete & Computational Geometry, 15, 73-105 (1996) · Zbl 0840.68119
[25] Meek, D. S.; Walton, D. J., Spiral arc spline approximation to a planar spiral, Journal Computational and Applied Mathematics, 107, 21-30 (1999) · Zbl 0932.65009
[26] Meek, D. S.; Walton, D. J., Approximating smooth planar curves by arc splines, Journal Computational and Applied Mathematics, 59, 221-231 (1995) · Zbl 0836.65010
[28] Seong, J.-K.; Elber, G.; Kim, M.-S., Trimming local and global self-intersections in offset curves/surfaces using distance maps, Computer-Aided Design, 38, 183-193 (2006)
[29] Shamos, M. I.; Hoey, D., Closest-point problems, (Proc. 16th Ann. IEEE Symp. Foundations of Computer Science (1975)), 151-162
[30] Sharir, M., Intersection and closest-pair problems for a set of circular discs, SIAM Journal on Computing, 14, 448-468 (1985) · Zbl 0564.68052
[31] Šír, Z.; Feichtinger, R.; Jüttler, B., Approximating curves and their offsets using biarcs and Pythagorean hodograph quintics, Computer-Aided Design, 38, 608-618 (2006)
[32] Yap, C.-K., An \(O(n \log n)\) algorithm for the Voronoi diagram of a set of simple curve segments, Discrete & Computational Geometry, 2, 365-393 (1987) · Zbl 0628.68042
[33] Yap, C.-K.; Alt, H., Motion planning in the CL-environment, (Lecture Notes in Computer Science, vol. 382 (1989)), 373-380 · Zbl 0767.68100
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.