Towards an Optimal Method for Dynamic Planar Point Location
Timothy M. Chan, Yakov Nekrich · SIAM Journal on Computing · 2018
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)^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(\log n)$ if the update time is increased to $O(\log^{1+\varepsilon}n)$ for any constant $\varepsilon>0$, or vice versa.