Computing Shortest Paths amidst Growing Discs in the Plane
Jur P. van den Berg, Mark H. Overmars · 2006
In this paper an algorithm is presented to find a short-est path between two points in the plane amidst grow-ing discs. That is, as the “point ” moves through the plane, the discs grow at an a priori known rate. We present an O(n3 logn) algorithm and a fast imple-mentation. The problem is motivated from robotics, where motion planning in dynamic environments is a great challenge. Our algorithm can be used to gen-erate paths in such environments guaranteeing that they will be collision-free in the future. 1