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(logn(log logn)(2)) 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(logn) if the update time is increased to O(log(l+epsilon) n) for any constant epsilon > 0, or vice versa.