  We present a method for guaranteed collision detection with toleranced
motions. The basic idea is to consider the motion as a curve in the
12-dimensional space of affine displacements, endowed with an object-oriented
Euclidean metric, and cover it with balls. The associated orbits of points,
lines, planes and polygons have particularly simple shapes that lend themselves
well to exact and fast collision queries. We present formulas for elementary
collision tests with these orbit shapes and we suggest an algorithm, based on
motion subdivision and computation of bounding balls, that can give a
no-collision guarantee. It allows a robust and efficient implementation and
parallelization. At hand of several examples we explore the asymptotic behavior
of the algorithm and compare different implementation strategies.
