On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles

Let ₁,..., _m bem simple Jordan curves in the plane, and letK₁,...,K_m be their respective interior regions. It is shown that if each pair of curves _i, _j,i j, intersect one another in at most two points, then the boundary ofK=_i^=1mK_i contains at most max(2,6m – 12) intersection points of the curves₁, and this bound cannot be improved. As a corollary, we obtain a similar upper bound for the number of points of local nonconvexity in the union ofm Minkowski sums of planar convex sets. Following a basic approach suggested by Lozano Perez and Wesley, this can be applied to planning a collision-free translational motion of a convex polygonB amidst several (convex) polygonal obstaclesA₁,...,A_m. Assuming that the number of corners ofB is fixed, the algorithm presented here runs in timeO (n log²n), wheren is the total number of corners of theA_i's.Work on this paper by the second author has been supported in part by a grant from the Bat-Sheva Fund at Israel. Work by the fourth author has been supported in part by a grant from the U.S.-Israeli Binational Science Foundation.