On translating ellipses amidst elliptic obstacles

We consider the problem of moving an elliptic object A, surrounded by a set of elliptic obstacles {Bj}. The initial and final positions of the object are known and the intention is to move A solely by performing translations in the plane. The motion must be performed in such a way that A does not collide with any of the obstacles. We present the following algorithms: (i) An algorithm, of complexity O(N log N), where N is the number of obstacles, which yields the set of all directions along which the object is separable from the obstacles by a single translation. (ii) An algorithm, quadratic in the number of obstacles, which yields a path for A to be moved from its starting configuration to its final configuration. The technique we propose first transforms the ellipse A into a circle A´. This same transformation changes each ellipse Bjinto another figure Bj´, which is also elliptic. The algorithms then compute the path of translation by processing the configuration obstacle space of {Bj´} with respect to the circle A´.