SOME COLLISION AVOIDANCE PROBLEMS BETWEEN SPHERES.

It is shown that a set of n spheres in 3-space, unlike convex polyhedra, exhibits the translation ordering property. Furthermore, such an ordering can be obtained in O(n log n) time. It is also proven that there always exist at least H spheres that can be translated to infinity without disturbing the others, where H is the number of spheres whose centers lie on the convex hull of the centers of the entire collection of spheres. In the worst case H equals minn, 4 and thus this strengthens the result of R. Dawson (1984). It also implies that at least H spheres can be identified with this property in O(n log n) time. Finally, for the two-dimensional problem, it is shown that for a given circle C//i in a collection of circles, all directions of allowable translations for C//i can be computed in O(n log n) time and, therefore, all circles that can be so translated individually without disturbing the others can be identified in O(n**2 log n) time. Some open problems are also discussed.