DYNAMIC POINT LOCATION IN GENERAL SUBDIVISIONS

The dynamic planar point location problem is the task of maintaining a dynamic set S of n nonintersecting (except possibly at endpoints) lin e segments in the plane under the following operations: Locate (q: poi nt): Report the segment immediately above q, i.e., the first segment i ntersected by an upward vertical ray starting at q; Insert (s: segment ): Add segment s to the collection S of segments; Delete (s: segment): Remove segment s from the collection S of segments. We present a solu tion which requires space O(n) and has query and insertion time O(log n log log n) and deletion time O(log2 n). The bounds for insertions an d deletions are amortized. A query time below O(log2 n) was previously only known for monotone subdivisions and subdivisions consisting of h orizontal segments and required nonlinear space. (C) 1994 Academic Pre ss, Inc.