Approximate Euclidean shortest paths amid convex obstacles
Lists
Only you see this
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...