Before revision: We study k nearest neighbor queries in the plane for general ( convex, pairwise disjoint ) sites of constant description complexity ( such as line segment , disks, quadrilaterals and so on) and with respect to a general family of distance functions including the L_p-norms and constant-size convex distance functions.
After revision: We study k nearest neighbor queries in the plane for general ( convex, pairwise disjoint ) sites of constant description complexity ( such as line segment , disks, quadrilaterals and so on) and with respect to a general family of distance functions including the L_p-norms and additively weighted Euclidean distances. For point sites in the Euclidean metric, after four decades of effort, an optimal data structure has recently been developed with O( n ) space, O( log n + k ) query time, and O( n log n ) preprocessing time.