Constructing Approximate Shortest Path Maps in Three Dimensions

Sariel Har-Peled

We define two results on approximate shortest path maps in R³.

1. Given a polyhedral surface or a convex polytope P with n edges in R³, a source point s on P, and a real parameter 0 < µ <= 1, we present an algorithm that computes a subdivision of P of size O((n/µ) log( 1/µ)) which can be used to answer efficiently approximate shortest path queries. Namely, given any point t on P, one can compute, in O( log(n/µ)) time, a distance L_P,s(t), such that d_P,s(t) <= L_P,s(t) <=(1 + µ)d_P,s(t), where d_P,s(t) is the length of a shortest path between s and t on P.

   The map can be computed in O(n² log n +(n/µ) log(1/µ) log(n/µ)) time, for the case of a polyhedral surface, and in O((n/µ³) log( 1/µ) +(n/µ^1.5) log(1/µ) log n) time if P is a convex polytope.

2. Given a set of polyhedral obstacles V with a total of n edges in R³, a source point s in R³ \setminus int \bigcup_{O in V} O, and a real parameter 0 < µ <= 1, we present an algorithm that computes a subdivision of R³, of size O(n² /µ^4+delta), for any delta > 0, which can be used to answer efficiently approximate shortest path queries. That is, for any point t in R³, one can compute, in O( log(n/µ)) time, a distance L_V,s(t), such that d_V,s(t) <= L_V,s(t) <=( 1+µ) d_V,s(t), where d_V,s( t) is the length of a shortest path from s to t that avoids the interiors of the obstacles. This subdivision can be computed in
   O((n⁴)/(µ²)((beta(n))/(µ⁴) log (n)/(µ) + log(nrho) log( n log rho )) log(1)/(µ) )
   time, where rho is the ratio of the length of the longest edge in V to the smallest Euclidean distance between s and any point of the obstacles, beta(n) = alpha(n) ^{O(alpha(n))^ O(1)} , and alpha(n) is the inverse of the Ackermann function.

Appeared in the 14th ACM Symp. of Comput. Geom., 1998
and SIAM J. Comput.

PS : PDF.

@article{h-caspm-99, 
  author  = "S.~Har-Peled",
  title   = {Constructing approximate shortest path maps in three
             dimensions},
  year    = 1999,
  journal = {SIAM J. Comput.},
  volume  = 28,
  number  = 4,
  pages   = {1182--1197},
}