Approximate Euclidean shortest paths amid convex obstacles


Journal Article

We develop algorithms and data structures for the approximate Euclidean shortest path problem amid a set P of k convex obstacles in ℝ2and ℝ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. Copyright © by SIAM.

Duke Authors

Cited Authors

  • Agarwal, PK; Sharathkumar, R; Yu, H

Published Date

  • September 21, 2009

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Start / End Page

  • 283 - 292

Citation Source

  • Scopus