PIECEWISE-LINEAR PATHS AMONG CONVEX OBSTACLES

Abstract

Let B be a set of n arbitrary (possibly intersecting) convex obstacles in R(d). It is shown that any two points which can be connected by a path avoiding the obstacles can also be connected by a path consisting of O(n((d-1)[d/2+1])) segments. The bound cannot be improved below Omega(n(d)); thus, in R(3), the answer is between n(3) and n(4). For open disjoint convex obstacles, a Theta(n) bound is proved. By a well-known reduction, the general case result also upper bounds the complexity for a translational motion of an arbitrary convex robot among convex obstacles. Asymptotically tight bounds and efficient algorithms are given in the planar case.