Polynomial time collision detection for manipulator paths specified by joint motions

An exact collision detection algorithm is described and analyzed. The time bound considers the complexity of the solids, the number of joints, and the number of distinct collision configurations. A bound for the number of collision configurations can be taken directly from the input data. The algorithm is based on an exact treatment of trigonometric expressions. The representation of trigonometric constants is discussed. Since all computations are exact, the distances between objects can be arbitrarily small. It is shown that collision detection can be performed in polynomial time. Other measures for the complexity of a motion with respect to collision detection could be based on minimal distances between objects. In this case smaller distances lead to increased computing time