Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235516] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Sharathkumar, R; Yu, H, Approximate Euclidean shortest paths amid convex obstacles, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (2009), pp. 283-292
    (last updated on 2018/10/20)

    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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320