A Unified Approach to Dynamic Point Location, Ray shooting, and Shortest Paths in Planar Maps
Yi‐Jen Chiang, Franco P. Preparata, Roberto Tamassia · SIAM Journal on Computing · 1996
We describe a new technique for dynamically maintaining the trapezoidal decomposition of a connected planar map $\mathcal{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 $\mathcal{M}$. The space requirement is $O(n\log n)$. Point-location queries take time $O(n\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). This is the first polylog-time dynamic data structure for shortest-path and ray-shooting queries. It is also the first dynamic point-location data structure for connected planar maps that achieves optimal query time.