ABSTRACT
In this article we consider the problem of efficient detection of intersection or proximity in a collection of bodies in two or three dimensional space. In two-dimensional space we use (generalized) Voronoi diagrams as a tool for solving these problems. We review basic properties of these diagrams and describe various efficient techniques for their construction. In three dimensional space Voronoi diagrams are no longer adequate for efficient intersection detection, and we present other, though less powerful, techniques for restricted classes of objects.
