Tech Report CS-92-07

A Unified Approach to Dynamic Point Location, Ray Shooting and Shortest Paths in Planar Maps

Yi-Jen Chiang, Franco P. Preparata and Roberto Tamassia

January 1992

Abstract:

We describe a new technique for dynamically maintaining the trapezoidal decomposition of a planar map $\cal M$ with $n$ vertices, and apply it to the development of a unified dynamic data structure that supports point-location, ray-shooting, and shortest-path queries in $\cal M$. The space requirement is $O(n\log n)$. Point-location queries take time $O(\log n)$. Ray-shooting and shortest-path queries take time $O(\log^3 n)$ (plus $O(k)$ time if the $k$ edges of the shortest path are reported in addition to its length). Updates consist of insertions and deletions of vertices and edges, and take $O(\log^3 n)$ time (amortized for vertex updates).

(complete text in pdf or gzipped postscript)