We have discovered an algorithm which dramatically reduces the computational burden required to detect collisions among many simultaneously moving objects. We have proposed to utilize bounds on the dynamics of the modelled object to efficiently schedule computations. Experiments recently confirmed this approach. We have tested this algorithm in the case of many spheres moving with randomly assigned velocity vectors. This is a worst case scenario since we can expect practical situations such as the motion of robot limbs to display a much higher degree of coherence which the algorithm exploits. Experiments with up to 40 simultaneously moving objets have displayed a sub-linear growth of the computational burden with the number of objects. Naive algorithms display a quadratic complexity.

V. Hayward, A. Foisy, S. Aubry, Y. Ghallab

Mon Nov 13 10:43:02 EST 1995