A vertex algorithm for collision detection

An algorithm for detecting the collision of moving objects is presented. The algorithm applies to polyhedral objects that can be represented as convex hulls of finite number of vertices in two- or three-dimensional space. This is then extended to a three- or four-dimensional space (respectively) to represent the objects and their motion. Nonlinear programming techniques are then employed to detect possible interference. The algorithm detects in one step whether or not the objects will interfere during their motion which may involve pure translations or rotations or both. A subalgorithm for computing the minimum distance between the objects is also presented. This can be used to solve the interference detection problem or for more general applications.