A UNIFIED APPROACH TO DYNAMIC POINT LOCATION, RAY SHOOTING, AND SHORTEST PATHS IN PLANAR MAPS

We describe a new technique for dynamically maintaining the trapezoida l decomposition of a connected planar map M with n vertices and apply it to the development of a unified dynamic data structure that support s point-location, ray-shooting, and shortest-path queries in M. The sp ace requirement is O(n log n). Point-location queries take time O(log n). Ray-shooting and shortest-path queries Lake time O(log(3) n) (plus O(k) time if the k edges of the shortest path are reported in additio n to its length). Updates consist of insertions and deletions of verti ces 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-loca tion data structure for connected planar maps that achieves optimal qu ery time.