Constructing Approximate Shortest Path Maps in Three Dimensions

# 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},
}
```