LP-based algorithms for detecting the collision of moving objects

This paper considers the problem of detecting the collision of moving objects in three-dimensional space. It develops two algorithms that use linear programming techniques to detect exact possible collisions between the objects in both time and space when the objects are represented as polyhedral sets in ℛ² or ℛ³. The algorithms can handle the case of a rigid body moving on a general path with simultaneous translation and rotation. Computational experience on the developed algorithms is also presented.