Title | ||
---|---|---|
An O ( n 2log n ) Time Algorithm for Computing Shortest Paths Amidst Growing Discs in the Plane |
Abstract | ||
---|---|---|
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(n
2logn) 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.
|
Year | DOI | Venue |
---|---|---|
2007 | 10.1007/978-3-540-77120-3_58 | ISAAC |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
4 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Anil Maheshwari | 1 | 869 | 104.47 |
Doron Nussbaum | 2 | 89 | 13.49 |
Jörg-Rüdiger Sack | 3 | 1099 | 166.07 |
Jiehua Yi | 4 | 17 | 1.98 |