On the problem of translating an elliptic object through a workspace of elliptic obstacles

Abstract

SUMMARY: Two algorithms are presented which deal with translating an elliptic object, A, without collision amidst elliptic obstacles. These are:(i) An exact algorithm, of complexity O(N log N), where N is the number of obstacles, yielding all directions along which the object is separable from the obstacles by a single translation.(ii) An algorithm quadratic in N, which yields, with a degree of approximation determined by the user, a path of the object from its initial to its final position.