LP-Based Algorithms for Detecting the Collision of Moving Objects

Abstract

In this paper, we consider the problem of detecting the collision of moving objects in three-dimensional space. We develop 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.

Keywords:

• collision detection
• linear programming