2026-07-22T11:39:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8738 2024-03-06T10:42:32Z ddc:004 open_access

Dynamic Planar Orthogonal Point Location in Sublogarithmic Time Chan, Timothy M. Tsakalidis, Konstantinos dynamic data structures point location word RAM We study a longstanding problem in computational geometry: dynamic 2-d orthogonal point location, i.e., vertical ray shooting among n horizontal line segments. We present a data structure achieving O(log n / log log n) optimal expected query time and O(log^{1/2+epsilon} n) update time (amortized) in the word-RAM model for any constant epsilon>0, under the assumption that the x-coordinates are integers bounded polynomially in n. This substantially improves previous results of Giyora and Kaplan [SODA 2007] and Blelloch [SODA 2008] with O(log n) query and update time, and of Nekrich (2010) with O(log n / log log n) query time and O(log^{1+epsilon} n) 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timothy M. Chan and Konstantinos Tsakalidis 2018 Is Part Of LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2018.25 urn:nbn:de:0030-drops-87382 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.25 eng https://creativecommons.org/licenses/by/3.0/legalcode