Approximate Euclidean shortest paths amid convex obstacles
Pankaj K. Agarwal, R. Sharathkumar, Hai Bo Yu · 2009
We develop algorithms and data structures for the approximate Euclidean shortest path problem amid a set P of k convex obstacles in R 2 and R 3, with a total of n faces. The running time of our algorithms is linear in n, and the size and query time of our data structure are independent of n. We follow a “core-set ” based approach, i.e., we quickly compute a small sketch Q of P whose size is independent of n and then compute approximate shortest paths with respect to Q. 1