Motion Planning amidst Fat Obstacles

The complexity of exact motion planning algorithms highly depends on the complexity of the robot’s free space, i.e., the set of all collision-free placements of the robot. Theoreti-cally, the complexity of the free space can be very high. In practice, the complexity of the free space tends to be much smaller. We show that, under some realistic assump-tions, the complexity of the free space of a robot moving amidst fat obstacles is linear in the number of obstacles. The complexity results lead to efficient algorithms for mo-tion planning amidst fat obstacles: we show that theOn motion planning algorithm by Schwartz and Sharir runs in On time if the obstacles are fat. Finally, we modify the algorithm to improve the running time toOn log n.