Non-Euclidean Optimal Path Problems
Zheng Sun
Hong Kong Baptist U

Date:  Friday, May 7, 2004.
Time:  11-12
Venue: Room 3464, HKUST


Abstract
--------
We introduce an approximation algorithm for the weighted region optimal
path problem. In this problem, a point robot moves in a planar space
composed of $n$ triangular regions, each of which is associated with a
positive unit weight. The objective is to find, for given source and
destination points $s$ and $t$, a path from $s$ to $t$ with the minimum
weighted length. Our algorithm, BUSHWHACK, adopts a traditional approach
that converts the original continuous geometric search space into a
discrete graph G by placing representative points on boundary edges.
However, by exploiting geometric structures that we call intervals,
BUSHWHACK computes an approximate optimal path more efficiently as it
accesses only a sparse subgraph of G. Combined with the logarithmic
discretization scheme introduced by Aleksandrov et. al., BUSHWHACK can
compute an $\epsilon$-approximation in $O(\frac{n}{\epsilon} (\log
\frac{1}{\epsilon} + \log n) \log \frac{1}{\epsilon})$ time. By reducing
complexity dependency on $\epsilon$, this result improves on all
previous results with the
same discretization approach. More importantly, this algorithm can be
generalized to a class of non-Euclidean optimal path problems, which we
call piecewise pseudo-Euclidean optimal path problems.