Piecewise linear paths among convex obstacles

Abstract

Let B be a set of n arbitrary (possibly intersecting) convex obstacles in Rd. 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 0(nId-l)ld/2+1~) segments. The bound cannot be improved below Q(nd); thus in R3, the answer is between n3 and n4. For disjoint obstacles, a ~(n) bound is proved. By a well-known reduction, thegeneralca.se result also upper bounds the complexity for a translational motion of an arbitrary convex robot among convex obstacles. In the planar case, asymptotically tight bounds and efficient algorithms are given.