DYNAMIC TREES AND DYNAMIC POINT LOCATION

This paper describes new methods for maintaining a point-location data structure for a dynamically changing monotone subdivision. The main a pproach is based on the maintenance of two interlaced spanning trees, one for and one S for the graph-theoretic planar dual of. Queries are answered by using a centroid decomposition S of the dual tree to drive searches in the S primal tree. These trees are maintained via the lin k-cut trees structure of Sleator and Tarjan [J. Comput. System Sci., 2 6 (1983), pp. 362-381], leading to a scheme that achieves vertex inser tion/deletion in O(log n) time, insertion/deletion of k-edge monotone chains in O(log n+k) time, and answers queries in O(log(2) n) time, wi th O(n) space, where n is the current size of subdivision S. The techn iques described also allow for the dual operations expand and contract to be implemented in O(log n) time, leading to an improved method for spatial point location in a 3-dimensional convex subdivision. In addi tion, the interlaced-tree approach is applied to on-line point locatio n (where one builds incrementally), improving the query bound to O(log n log log n) time and the update bounds to O(1) S amortized time in t his case. This appears to be the first on-line method to achieve a pol ylogarithmic query time and constant update time.