Abstract
We are interested in Voronoi diagrams as a tool in robot path planning, where the search for a path in anr-dimensional space may be simplified to a search on an (r−1)-dimensional Voronoi diagram. We define a Voronoi diagramV based on a measure of distance which is not a true metric. This formulation has lower algebraic complexity than the usual definition, which is a considerable advantage in motion-planning problems with many degrees of freedom. In its simplest form, the measure of distance between a point and a polytope is the maximum of the distances of the point from the half-spaces which pass through faces of the polytope. More generally, the measure is defined in configuration spaces which represent rotation. The Voronoi diagram defined using this distance measure is no longer a strong deformation retract of free space, but it has the following useful property: any path through free space which starts and ends on the diagram can be continuously deformed so that it lies entirely on the diagram. Thus it is still complete for motion planning, but it has lower algebraic complexity than a diagram based on the Euclidean metric.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Canny, J. F., A Voronoi method for the piano-movers problem,Proc. IEEE Int. Conf. Robotics and Automation, St. Louis, MO, March 1985.
Canny, J. F., Collision detection for moving polyhedra,IEEE Trans. PAMI (1986a)8.
Canny, J. F., Constructing roadmaps of semi-algebraic sets,Proc. Int. Workshop on Geometric Reasoning, Oxford University, June 1986b.
Donald, B. R., Motion Planning with Six Degrees of Freedom, MIT AI-TR-791, MIT Artificial Intelligence Lab., 1984.
Lee, D. T. and Drysdale, R. L., Generalization of Voronoi diagrams in the plane,SIAM J. Comput. 10 (1981), 73–87.
Lozano-Pérez, T., Spatial planning: a configuration space approach,IEEE Trans. Comput. 32 (1983), 108–120.
Lozano-Pérez, T. and Wesley, M., An algorithm for planning collision-free paths among polyhedral obstacles,Comm. ACM 22 (1979), 560–570.
Ó'Dúnlaing, C., Sharir, M., and Yap, C., Generalized Voronoi Diagrams for Moving a Ladder: I Topological Analysis, Robotics Lab. Tech. Report No. 32, NYU-Courant Institute, (1984).
Ó'Dúnlaing, C., Sharir, M., and Yap, C., Generalized Voronoi Diagrams for Moving a Ladder: II Efficient Construction of the Diagram, Robotics Lab. Tech. Report No. 33, NYU-Courant Institute (1984).
Ó'Dúnlaing, C. and Yap, C., A retraction method for planning the motion of a disc,J. Algorithms,6 (1985), 104–111.
Schwartz, J. and Sharir, M., On the “Piano Movers” Problem, II. General Techniques for Computing Topological Properties of Real Algebraic Manifolds, Report No. 41, Comp. Sci. Dept., New York University 1982.
Schwartz, J. and Yap, C. K.,Advances in Robotics, Lawrence Erlbaum Associates, Hillside, New Jersey, 1986.
Whitney, H., Elementary structure of real algebraic varieties,Ann. of Math. 66 (1957), 3.
Yap, C., Coordinating the Motion of Several Discs, Robotics Lab. Tech. Report No. 16, NYU-Courant Institute (1984).
Author information
Authors and Affiliations
Additional information
This report describes research done at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for the Laboratory's Artificial Intelligence research is provided in part by the Office of Naval Research under Office of Naval Research Contract N00014-81-K-0494 and in part by the Advanced Research Projects Agency under Office of Naval Research Contracts N00014-85-K-0124 and N00014-82-K-0334. John Canny was supported by an IBM fellowship. Bruce Donald was funded in part by a NASA fellowship administered by the Jet Propulsion Laboratory.
Rights and permissions
About this article
Cite this article
Canny, J., Donald, B. Simplified Voronoi diagrams. Discrete Comput Geom 3, 219–236 (1988). https://doi.org/10.1007/BF02187909
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02187909