Tech Report CS-94-03

Optimal Shortest Path and Minimum-Link Path Queries Between Two Convex Polygons in the Presence of Obstacles

Yi-Jen Chiang and Roberto Tamassia

February 1994


We present efficient algorithms for shortest-path and minimum-link-path queries between two convex polygons inside a simple polygon $P$, which acts as an obstacle to be avoided. Let $n$ be the number of vertices of $P$, and $h$ the total number of vertices of the query polygons. We show that shortest-path queries can be performed optimally in time $O(\log h +\log n)$ (plus $O(k)$ time for reporting the $k$ edges of the path) using a data structure with $O(n)$ space and preprocessing time, and that minimum-link-path queries can be performed in optimal time $O(\log h+\log n)$ (plus $O(k)$ to report the $k$ links), with $O(n^3)$ space and preprocessing time.

We also extend our results to the dynamic case, and give a unified data structure that supports both queries for convex polygons in the same region of a connected planar subdivision $\cal S$. The update operations consist of insertions and deletions of edges and vertices. Let $n$ be the current number of vertices in $\cal S$. The data structure uses $O(n)$ space, supports updates in $O(\log^2 n)$ time, and performs shortest-path and minimum-link-path queries in times $O(\log h +\log^2 n)$ (plus $O(k)$ to report the $k$ edges of the path) and $O(\log h+k\log^2 n)$, respectively. Performing shortest-path queries is a variation of the well-studied {\em separation} problem, which has not been efficiently solved before in the presence of obstacles. Also, it was not previously known how to perform minimum-link-path queries in a dynamic environment, even for two-point queries.

(complete text in pdf or gzipped postscript)