TOWARDS AN OPTIMAL METHOD FOR DYNAMIC PLANAR POINT LOCATION

作     者：Chan, Timothy M. Nekrich, Yakov 

作者机构：Univ Illinois Dept Comp Sci Urbana IL 61801 USA Univ Waterloo Cheriton Sch Comp Sci Waterloo ON N2L 3G1 Canada 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：2018年第47卷第6期

页      面：2337-2361页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：NSERC 

主　　题：point location dynamic data structures computational geometry 

摘      要：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(logn(log logn)(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(logn) if the update time is increased to O(log(l+epsilon) n) for any constant epsilon 0, or vice versa.