HaiYu .Approximate Euclidean Shortest Paths amid Convex Obstacles

We develop algorithms and data structures for the approx-imate 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 com-pute a small sketch Q of P whose size is independent of n and then compute approximate shortest paths with respect to Q.