ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract Let γ1,..., γ m bem simple Jordan curves in the plane, and letK 1,...,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 =1m K i contains at most max(2,6m − 12) intersection points of the curvesγ 1, 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 1,...,A m . Assuming that the number of corners ofB is fixed, the algorithm presented here runs in timeO (n log2 n), wheren is the total number of corners of theA i 's.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02187683
Permalink