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.
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.