TY - GEN
T1 - Towards an Optimal Method for Dynamic Planar Point Location
AU - Chan, Timothy M.
AU - Nekrich, Yakov
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2015/12/11
Y1 - 2015/12/11
N2 - We describe a fully dynamic linear-space data structure for point location in connected planar subdivisions, or more generally vertical ray shooting among non-intersecting line segments, that supports queries in O(logn(loglogn)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(logn 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+∈n) for any constant ∈ > 0, or vice versa.
AB - We describe a fully dynamic linear-space data structure for point location in connected planar subdivisions, or more generally vertical ray shooting among non-intersecting line segments, that supports queries in O(logn(loglogn)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(logn 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+∈n) for any constant ∈ > 0, or vice versa.
UR - http://www.scopus.com/inward/record.url?scp=84960384736&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84960384736&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2015.31
DO - 10.1109/FOCS.2015.31
M3 - Conference contribution
AN - SCOPUS:84960384736
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 390
EP - 409
BT - Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015
PB - IEEE Computer Society
T2 - 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015
Y2 - 17 October 2015 through 20 October 2015
ER -