An O(n2log n) time algorithm for computing shortest paths amidst growing discs in the plane

We present an algorithm to compute a shortest path for a robot between two points that avoids n discs growing at a common speed in the plane. Our algorithm runs in O(n2 log n) time, thus improving upon the best previous solution by a factor of n. The complexity for the growing disc problem matches the known bound for the more restricted case when the discs are static.