We define two results on approximate shortest path maps in R3.
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.
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(n2
/µ4+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.