  Given a set $\mathcal{P}$ of $h$ pairwise disjoint simple polygonal obstacles
in $\mathbb{R}^2$ defined with $n$ vertices, we compute a sketch $\Omega$ of
$\mathcal{P}$ whose size is independent of $n$, depending only on $h$ and the
input parameter $\epsilon$. We utilize $\Omega$ to compute a
$(1+\epsilon)$-approximate geodesic shortest path between the two given points
in $O(n + h((\lg{n}) + (\lg{h})^{1+\delta} +
(\frac{1}{\epsilon}\lg{\frac{h}{\epsilon}})))$ time. Here, $\epsilon$ is a user
parameter, and $\delta$ is a small positive constant (resulting from the time
for triangulating the free space of $\cal P$ using the algorithm in
\cite{journals/ijcga/Bar-YehudaC94}). Moreover, we devise a
$(2+\epsilon)$-approximation algorithm to answer two-point Euclidean distance
queries for the case of convex polygonal obstacles.

Computational Geometry