An O(n2) shortest path algorithm for a non-rotating convex body
John E. Hershberger, Leonidas Guibas · Journal of Algorithms · 1988
We investigate the problem of moving a convex body in the plane from one location to another while avoiding a given collection of polygonal obstacles. The method we propose is applicable when the convex body is not allowed to rotate. If n denotes the total size of all polygonal obstacles, the method yields an O(n2) algorithm for finding a shortest path from the initial to the final location. In solving this problem, we develop some new tools in computational geometry that may be of independent interest.