On the problem of translating an elliptic object through a workspace of elliptic obstacles
B. John Oommen, Irwin Reichstein · Robotica · 1987
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.