Dynamic Planar Orthogonal Point Location in Sublogarithmic Time

We study a longstanding problem in computational geometry: dynamic 2-d orthogonal point location, i.e., vertical ray shooting among nnn horizontal line segments. We present a data structure achieving O(lognloglogn)O(log⁡nlog⁡log⁡n)O\left(\frac{\log n}{\log \log n}\right) optimal expected query time and O(log1/2+en)O(log1/2+e⁡n)O\left(\log^{1/2+\varepsilon}n\right) update time (amortized) in the word-RAM model for any constant e>0e>0\varepsilon>0, under the assumption that the xxx-coordinates are integers bounded polynomially in nnn. This substantially improves previous results of Giyora and Kaplan [SODA 2007] and Blelloch [SODA 2008] with O(logn)O(log⁡n)O\left(\log n\right) query and update time, and of Nekrich (2010) with O(lognloglogn)O(log⁡nlog⁡log⁡n)O\left(\frac{\log n}{\log \log n}\right) query time and O(log1+en)O(log1+e⁡n)O\left(\log^{1+\varepsilon}n\right) update time. Our result matches the best known upper bound for simpler problems such as dynamic 2-d dominance range searching. We also obtain similar bounds for orthogonal line segment intersection reporting queries, vertical ray stabbing, and vertical stabbing-max, improving previous bounds, respectively, of Blelloch [SODA 2008] and Mortensen [SODA 2003], of Tao (2014), and of Agarwal, Arge, and Yi [SODA 2005] and Nekrich [ISAAC 2011].