Approximate Euclidean shortest paths amid convex obstacles

Pankaj K. Agarwal, R. Sharathkumar, Hai YuSODA 2009 · OpenReview

Abstract

We develop algorithms and data structures for the approximate Euclidean shortest path problem amid a set P of K convex obstacles in R2 and R3, 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.
BibTeX
@inproceedings{agarwal2009approximate,
  author = {Pankaj K. Agarwal and R. Sharathkumar and Hai Yu},
  title = {{Approximate Euclidean shortest paths amid convex obstacles}},
  booktitle = {SODA},
  year = {2009},
  url = {https://openreview.net/forum?id=5qZUbNZeGw},
}

Loading related content...

Figure