Constructing Approximate Shortest Path Maps in Three Dimensions

We present a new technique for constructing a data structure that approximates shortest path maps in ᵈ. By applying this technique, we get the following two results on approximate shortest path maps in ³. (i) Given a polyhedral surface or a convex polytope with n edges in ³, a source point s on , and a real parameter 0 < ≤ 1, we present an algorithm that computes a subdivision of of size O((n/) log( 1/ )) which can be used to answer efficiently approximate shortest path queries. Namely, given any point t on , one can compute, in O(log(n/)) time, a distance Δ,s(t), such that d,s(t) ≤ Δ,s(t) ≤ (1 + )d,s(t), where d,s(t) is the length of a shortest path between s and t on . The map can be computed in O(n² logn + (n/) log(1/) log(n/)) time, for the case of a polyhedral surface, and in O((n/³) log ( 1/ ) + (n/1.5) log(1/) logn) time if is a convex polytope. (ii) Given a set of polyhedral obstacles with a total of n edges in ³, a source point { s} in ³ ∪O ∈ O, and a real parameter 0 < ≤ 1, we present an algorithm that computes a subdivision of ³, which can be used to answer efficiently approximate shortest path queries. That is, for any point t ∈ ³, one can compute, in O(log(n/)) time, a distance Δ,s(t) that -approximates the length of a shortest path from { s} to { t} that avoids the interiors of the obstacles. This subdivision can be computed in roughly O(n⁴/⁶) time.