ABSTRACT
The past decade has brought significant progress in the development of algorithms for solving problems which are geometric in nature (see e.g., Lee & Preparata, 1984). Many of these algorithms depend on methods that were developed to solve problems in other branches of computer science. We believe that this trend will continue and that the methodology of computational geometry will ultimately find significant applications in robotics. Here we present and explain the methods used in developing three families of geometric algorithms. Two of these methods involve the decomposition of a problem into subproblems which can be more easily solved. The third involves transforming a problem in its entirety to a new format which may be more tractable.
