We define two results on approximate shortest path maps in R^{3}.
Given a polyhedral surface or a convex polytope P
with n edges in R^{3}, 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^{2} 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.
Given a set
of polyhedral obstacles V with a total of n edges
in R^{3}, a source point s in R^{3}
\setminus int \bigcup_{O in V} O, and a real parameter
0 < µ <= 1, we present an algorithm that computes
a subdivision of R^{3}, of size O(n^{2}
/µ^{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^{3}, 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^{4})/(µ^{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.