dynamic point location in general subdivisions
The dynamic planar point location problem is the task of maintaining a dynamic set S of n non-intersecting, except possibly at endpoints, line segments in the plane under the following operations: Locate( q point): Report the segment immediately above q , i.e., the first segment intersected by an upward vertical ray starting at q ; Insert( s segment): Add segment s to the collection S segments; Delete( s segment): Remove segment s from the collection S of segments. We present a solution which requires space O ( n ), has query and insertion time O (log n loglog n ) and deletion time O (log 2 n ). A query time below O (log 2 n ) was previously only known for monotone subdivisions and horizontal segments and required non-linear space.
dynamic point locatability general subdivision task segmentation operability collect space query timing log