Piecewise linear paths among convex obstacles
Mark de Berg, Jiřı́ Matoušek, Otfried Cheong Schwarzkopf · 1993
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.seresult 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.1