Divide-and-conquer for Voronoi diagrams revisited

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.

REFERENCES

• 1: O. Aichholzer , W. Aigner , F. Aurenhammer , T. Hackl , B. Jüttler , M. Rabl, Medial axis computation for planar free-form shapes, Computer-Aided Design, v.41 n.5, p.339-349, May, 2009 [doi>10.1016/j.cad.2008.08.008]
• 2: O. Aichholzer, F. Aurenhammer, T. Hackl, B. Jüttler, M.Oberneder, and Z. Sír. Computational and structural advantages of circular boundary representation. In Springer Lecture Notes in Computer Science, volume 4619, pages 374--385, 2007.
• 3: Helmut Alt , Otfried Cheong , Antoine Vigneron, The Voronoi Diagram of Curved Objects, Discrete & Computational Geometry, v.34 n.3, p.439-453, September 2005 [doi>10.1007/s00454-005-1192-0]
• 4: Lixin Cao , Jian Liu, Computation of medial axis and offset curves of curved boundaries in planar domain, Computer-Aided Design, v.40 n.4, p.465-475, April, 2008 [doi>10.1016/j.cad.2008.01.002]
• 5: CGAL. Computational Geometry Algorithms Library. http://www.cgal.org/.
• 6: Bernard Chazelle, A theorem on polygon cutting with applications, Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, p.339-349, November 03-05, 1982
• 7: L. Paul Chew , Robert L. (Scot) Dyrsdale, III, Voronoi diagrams based on convex distance functions, Proceedings of the first annual symposium on Computational geometry, p.235-244, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323264]
• 8: F.Y.L. Chin, J. Snoeyink, and C.A. Wang. Finding the medial axis of a simple polygon in linear time. Discrete & Computational Geometry, 21:405--420, 1999.
• 9: H.I. Choi, S.W. Choi, and H.P. Moon. Mathematical theory of medial axis transform. Pacific Journal of Mathematics, 181:57--88, 1997.
• 10: G. Elber, E. Cohen, and S. Drake. MATHSM: Medial axis transform toward high speed machining of pockets. Computer-Aided Design, 37:241--250, 2005.
• 11: Ioannis Z. Emiris , Elias P. Tsigaridas , George M. Tzoumas, The predicates for the Voronoi diagram of ellipses, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137891]
• 12: S. Fortune. A sweep line algorithm for Voronoi diagrams. Algorithmica, 2:153--174, 1987.
• 13: M. Held. Voronoi diagrams and offset curves of curvilinear polygons. Computer-Aided Design, 30(4):287--300, 1998.
• 14: Martin Held, VRONI: an engineering approach to the reliable and efficient computation of voronoi diagrams of points and line segments, Computational Geometry: Theory and Applications, v.18 n.2, p.95-123, March 2001 [doi>10.1016/S0925-7721(01)00003-7]
• 15: Martin Held , Stefan Huber, Topology-oriented incremental computation of Voronoi diagrams of circular arcs and straight-line segments, Computer-Aided Design, v.41 n.5, p.327-338, May, 2009 [doi>10.1016/j.cad.2008.08.004]
• 16: M. Held, G. Lukacs, and L. Andor. Pocket machining based on contour-parallel tool paths generated by means of proximity maps. Computer-Aided Design, pages 189--203, 1994.
• 17: David G. Kirkpatrick, Efficient computation of continuous skeletons, Proceedings of the 20th Annual Symposium on Foundations of Computer Science, p.18-27, October 29-31, 1979
• 18: R. Klein. Concrete and Abstract Voronoi diagrams. Springer Lecture Notes in Computer Science 400, 1990.
• 19: Rolf Klein , Kurt Mehlhorn , Stefan Meiser, Randomized incremental construction of abstract Voronoi diagrams, Computational Geometry: Theory and Applications, v.3 n.3, p.157-184, Aug. 1993 [doi>10.1016/0925-7721(93)90033-3]
• 20: D.T. Lee. Medial axis transformation of a planar shape. IEEE Trans. Pattern Analysis and Machine Intelligence, 4:363--369, 1982.
• 21: D.T. Lee and R.L.S. Drysdale. Generalization of Voronoi diagrams in the plane. SIAM Journal on Computing, 10:73--87, 1981.
• 22: M. McAllister, D. Kirkpatrick, and J. Snoeyink. A compact piecewise-linear Voronoi diagram for convex sites in the plane. Discrete & Computational Geometry, 15:73--105, 1996.
• 23: D. S. Meek , D. J. Walton, Spiral arc spline approximation to a planar spiral, Journal of Computational and Applied Mathematics, v.107 n.1, p.21-30, July 15, 1999 [doi>10.1016/S0377-0427(99)00072-2]
• 24: D. S. Meek , D. J. Walton, Approximating smooth planar curves by arc splines, Journal of Computational and Applied Mathematics, v.59 n.2, p.221-231, May 19, 1995 [doi>10.1016/0377-0427(94)00029-Z]
• 25: E. Pilgerstorfer. Asymptotischer Vergleich verschiedener Verfahren der Biarc-Approximation. Master Thesis, Johannes Kepler University Linz, Austria, 2008.
• 26: J-K. Seong, G. Elber, and M--S. Kim. Trimming local and global self-intersections in offset curves/surfaces using distance maps. Computer-Aided Design, 38:183--193, 2006.
• 27: Michael Ian Shamos , Dan Hoey, Closest-point problems, Proceedings of the 16th Annual Symposium on Foundations of Computer Science, p.151-162, October 13-15, 1975
• 28: M. Sharir. Intersection and closest-pair problems for a set of circular discs. SIAM Journal on Computing, 14:448--468, 1985.
• 29: Z. S'ır, R. Feichtinger, and B. Jüttler. Approximating curves and their offsets using biarcs and Pythagorean hodograph quintics. Computer-Aided Design, 38:608--618, 2006.
• 30: C.-K. Yap. An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments. Discrete & Computational Geometry, 2:365--393, 1987.
• 31: Chee-Keng Yap , Helmut Alt, Motion Planning in the CL-Environment (Extended Abstract), Proceedings of the Workshop on Algorithms and Data Structures, p.373-380, August 17-19, 1989

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
biarc approximation, divide-and-conquer, medial axis, motion planning, trimmed offset, voronoi diagram