Approximate Euclidean shortest paths amid convex obstacles

Published

Journal Article

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

Full Text

Duke Authors

Cited Authors

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

Published Date

  • January 1, 2009

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Start / End Page

  • 283 - 292

Digital Object Identifier (DOI)

  • 10.1137/1.9781611973068.32

Citation Source

  • Scopus