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.

Additional Metadata
Citation
Maheshwari, A, Nussbaum, D, Sack, J.-R, & Yi, J. (Jiehua). (2007). An O(n2log n) time algorithm for computing shortest paths amidst growing discs in the plane.