TY - GEN
T1 - Dynamic planar orthogonal point location in sublogarithmic time
AU - Chan, Timothy M.
AU - Tsakalidis, Konstantinos
N1 - Publisher Copyright:
© Timothy M. Chan and Konstantinos Tsakalidis; licensed under Creative Commons License CC-BY 34th Symposium on Computational Geometry (SoCG 2018).
PY - 2018/6/1
Y1 - 2018/6/1
N2 - 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(log1/2+ϵ n) update time (amortized) in the word-RAM model for any constant ϵ > 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 (log1+ϵ 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].
AB - 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(log1/2+ϵ n) update time (amortized) in the word-RAM model for any constant ϵ > 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 (log1+ϵ 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].
KW - Dynamic data structures
KW - Point location
KW - Word RAM
UR - http://www.scopus.com/inward/record.url?scp=85048978101&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85048978101&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.SoCG.2018.25
DO - 10.4230/LIPIcs.SoCG.2018.25
M3 - Conference contribution
AN - SCOPUS:85048978101
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 251
EP - 2515
BT - 34th International Symposium on Computational Geometry, SoCG 2018
A2 - Toth, Csaba D.
A2 - Speckmann, Bettina
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 34th International Symposium on Computational Geometry, SoCG 2018
Y2 - 11 June 2018 through 14 June 2018
ER -