The complexity of the free space for a robot moving amidst fat obstacles
A. F. Vanderstappen, Dan Halperin, M.H. Overmars · 1992
We propose a new definition of fatness of a geometric object and compare it with alternative definitions. We show that, under some realistic assumptions, the complexity of the free space for a robot with any fixed number of degrees of freedom moving in a d-dimensional Euclidean workspace with fat obstacles is linear in the number of obstacles. The complexity of motion planning algorithms depends, to a large extent, on the complexity of the robot's free space, and theoretically, the complexity of the free space can be very high. Thus, our result opens the way to devising efficient motion planning algorithms in certain realistic settings. 1 Introduction It has been recently noted that, in certain problems in computational geometry, the relatively high complexity implied by worst-case lower bound constructions, can be avoided if we assume that the objects at hand have a certain "fatness" property. This paper discusses fatness in the context of algorithmic motion planning. 1.1 Background:...