TY - CONF

T1 - SOME COLLISION AVOIDANCE PROBLEMS BETWEEN SPHERES.

AU - Toussaint, Godfried T.

PY - 1985

Y1 - 1985

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0022324933&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0022324933&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0022324933

SP - 291

EP - 295

ER -