ABSTRACT
Sharir and Leven (Intersection and Proximity Problems and Voronoi Diagrams) deepen a theme opened in Chapters 2 and 3, namely the use of Voronoi diagrams (which are defined to be the subspaces consisting of all those points, lying within larger abstract spaces of "positions," which represent "critical positions" in one or another sense, e.g., positions simultaneously nearest to several of a given collection of points or other geometric elements). Such diagrams have turned out to be among the most versatile and effective structures in computational geometry, having application in such diverse areas as motion planning, geometric searching, pattern recognition, computational fluid dynamics, solid state physics, chemistry, and statistics. Sharir and Leven review some of the most important applications of this technique to robotics and describe many of the most efficient algorithmic techniques known for calculating and for applying Voronoi diagrams.
