DYNAMIC RAY SHOOTING AND SHORTEST PATHS IN PLANAR SUBDIVISIONS VIA BALANCED GEODESIC TRIANGULATIONS

We give new methods for maintaining a data structure that supports ray -shooting and shortest-path queries in a dynamically changing connecte d planar subdivision L. Our approach is based on a new dynamic method for maintaining a balanced decomposition of a simple polygon via geode sic triangles. We maintain such triangulations by viewing their dual t rees as balanced trees. We show that rotations in these trees can be i mplemented via simple ''diagonal swapping'' operations performed on th e corresponding geodesic triangles, and that edge insertion and deleti on can be implemented on these trees using operations akin to the stan dard split and splice operations. We also maintain a dynamic point loc ation structure on the geodesic triangulation, so that we may implemen t ray-shooting queries by first locating the ray's endpoint and then w alking along the ray from geodesic triangle to geodesic triangle until we hit the boundary of some region of L. The shortest path between tw o points in the same region is obtained by locating the two points and then walking from geodesic triangle to geodesic triangle either follo wing a boundary or taking a shortcut through a common tangent. Our dat a structure uses O(n) space and supports queries and updates in O(log( 2) n) worst-case time, where n. is the current size of L. It outperfor ms the previous best data structure for this problem by a log n factor in all the complexity measures (space, query times, and update times) . (C) 1997 Academic Press.