TOWARDS AN OPTIMAL METHOD FOR DYNAMIC PLANAR POINT LOCATION.

We describe a fully dynamic linear-space data structure for point location in connected planar subdivisions, or more generally vertical ray shooting among nonintersecting line segments, that supports queries in O(log n(log log n)²) time and updates in O(log n log log n) time. This is the first data structure that achieves close to logarithmic query and update time simultaneously, ignoring log log n factors. We further show how to reduce the query time to O(log n log log n) in the RAM model with randomization. Alternatively, the query time can be lowered to O(log n) if the update time is increased to O(log1+ε n) for any constant ε > 0, or vice versa. [ABSTRACT FROM AUTHOR]