Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions

摘要: We study the k nearest neighbors problem in plane for general, convex, pairwise disjoint sites of constant description complexity such as line segments, disks, and quadrilaterals with respect to a general family distance functions including L_p-norms additively weighted Euclidean distances. For point metric, after four decades effort, an optimal data structure has recently been developed O( n ) space, log + query time, preprocessing time. develop static setting nearly expected polylog The space approaches linear whose achievability is still unknown improves so far best ( log^2 )( )^2 Bohler et al.'s work. Our dynamic version (that allows insertions deletions sites) also reduces Kaplan work from log^3 ). To obtain these progresses, we devise shallow cuttings size functions. Shallow are key technique deal metric. Agarwal al. already designed linear-size functions, but their could not be applied problem. Recently, constructed that feasible problem, while extra double logarithmic factor. innovation new random sampling analysis geometric structures. Since our provides way analyze algorithms, believe it independent interest.