Math @ Duke

Publications [#235516] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Sharathkumar, R; Yu, H, Approximate Euclidean shortest paths amid convex obstacles,
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
(2009),
pp. 283292
(last updated on 2017/12/17)
Abstract: 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 "coreset" 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

