The study of minimum paths on or around polyhedra in Euclidean 3-space is of growing importance in robotics. This work presents new algorithms based on extensions of the Voronoi diagram. Since experience with new algo- rithms is also important, this work also describes a workbench to allow experimentation.

This book is based on the Ph.D. research of my former student, Varol Akman, who graduated from the Electrical, Computer, and Systems Engineer- ing Dept. of Rensselaer Polytechnic Institute in August 1985.

We wish to thank the other members of his committee: Frank DiCesare, Mukkai S. Krishnamoorthy, and James M. Tien. We also wish to thank Herbert Freeman for employing him in the Image Processing Lab at RPI, Michael J. Wozny for employing him in the Center for Interactive Com- puter Graphics, and Edwin Rogers for granting free access to the Computer Science Dept. facilities.

This research has been supported by the National Science Foundation under grants ECS 80-21504 and ECS 83-51942, by the Schlumberger-Doll Research Center, Ridgefield, Connecticut, USA, by a Fulbright Award, and by the Middle East Technical University, Ankara, Turkey. The views expressed in this work are those of the author alone, and no endorsement is expressed or implied by the support.