Abstract

Given a set of polygonal obstacles of $n$ vertices in the plane,
the problem of processing the all-pairs Euclidean {\em short} path
queries is that of reporting an obstacle-avoiding path $P$ (or
its length) between two arbitrary query points $p$ and $q$ in the 
plane, such that the length of $P$ is within a small factor of the 
length of a Euclidean {\em shortest} obstacle-avoiding path between
$p$ and $q$.  The goal is to answer each short path query quickly
by constructing data structures that capture path information in 
the obstacle-scattered plane.  For the related all-pairs Euclidean 
{\em shortest} path problem, the best known algorithms for even 
very simple cases (e.g., {\em rectilinear} shortest paths among 
disjoint {\em rectangular} obstacles in the plane) require
at least quadratic space and time to construct a data structure,
so that a length query can be answered in polylogarithmic time.  
The previously best known solution to the all-pairs Euclidean 
{\em short} path problem also uses a data structure of quadratic 
space and superquadratic construction time, in order to answer a 
length query in polylogarithmic time.  In this paper, we present a 
data structure that requires nearly linear space and takes subquadratic 
time to construct.  Precisely, for any given $\epsilon$ satisfying 
$0$ $<$ $\epsilon$ $\leq$ $1$, our data structure can be built
in $o(q^{3/2})$ $+$ $O((n\log n)/\epsilon)$ time and 
$O(n\log n+n/\epsilon)$ space, where $q$, $1$ $\leq$ $q$ $\leq$ $n$, 
is the minimum number of faces needed to cover all the vertices of 
a certain planar graph we use.  This data structure enables us to 
report the length of a short path between two arbitrary query points
in $O((\log n)/\epsilon+1/\epsilon^2)$ time and the actual path
in $O((\log n)/\epsilon+1/\epsilon^2+L)$ time, where $L$ is the 
number of edges of the output path.  The constant approximation 
factor, $6+\epsilon$, for the short paths that we compute is quite 
small.  Our techniques are parallelizable and can also be used 
to improve the previously best known results on several related 
graphic and geometric problems.