Constructing Approximate Shortest Path Maps in Three Dimensions
Home Bookmarks Papers Blog

Constructing Approximate Shortest Path Maps in Three Dimensions

Sariel Har-Peled


We define two results on approximate shortest path maps in R3.

  1. Given a polyhedral surface or a convex polytope P with n edges in R3, 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 LP,s(t), such that dP,s(t) <= LP,s(t) <=(1 + µ)dP,s(t), where dP,s(t) is the length of a shortest path between s and t on P.

    The map can be computed in O(n2 log n +(n/µ) log(1/µ) log(n/µ)) time, for the case of a polyhedral surface, and in O((n/µ3) 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 R3, a source point s in R3 \setminus int \bigcupO in V O, and a real parameter 0 < µ <= 1, we present an algorithm that computes a subdivision of R3, of size O(n24+delta), for any delta > 0, which can be used to answer efficiently approximate shortest path queries. That is, for any point t in R3, one can compute, in O( log(n/µ)) time, a distance LV,s(t), such that dV,s(t) <= LV,s(t) <=( 1+µ) dV,s(t), where dV,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((n4)/(µ2)((beta(n))/(µ4) 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},
}


Last modified: Fri Nov 14 11:15:51 CST 2014