an efficient algorithm for planning collision-free translational motion of a convex polygonal object in 2-dimensional space amidst polygonal obstacles
We state and prove a theorem about the number of points of local nonconvexity in the union of m . Minkowski sums of planar convex sets, and then apply it to planning a collision-free translational motion of a convex polygon B amidst several (convex) polygonal obstacles A l ,, A m , following a basic approach suggested by Lozano-Perez and Wesley. Assuming that the number of corners of B is fixed, the algorithm developed here runs in time &Ogr; ( n log 2 n ), where n is the total number of corners of the A l 's.
efficiency algorithm plan motion polygon object space point locality timing collision