Group nearest-neighbor queries in the L1 L 1 plane ?
Let P be a set of n points in the plane. The k-nearest-neighbor (abbreviated as k-NN) query problem is to preprocess P into a data structure that quickly reports k closest points in P for a query point q. This paper addresses a generalization of the k-NN query problem to a query set Q of points, namely, the group k -nearest-neighbor query problem, in the L1 L 1 plane. More precisely, a query is assigned with a set Q of at most m points and a positive integer k  with k?n k ? n , and the distance between a point p of P and a query set Q  is defined as the sum of L1 L 1 distances from p  to all q?Q q ? Q . The maximum number m of query points Q is assumed to be known in advance and to be at most n. In this paper, we propose two algorithms, one based on the range tree and the other based on a data structure for segment dragging queries, and obtain the following complexity bounds: (1) a group k -NN query can be handled in O(Tminlog?n+(k+m2)(log?log?n+log?m)) O ( T min log ? n + ( k + m 2 ) ( log ? log ? n + log ? m ) ) time after preprocessing P  using O(m2nlog2?n) O ( m 2 n log 2 ? n ) space, where Tmin=min?{k+m,m2} T min = min ? { k + m , m 2 } , or (2) a group k -NN query can be handled in O((k+m)log2?n+m2(log??n+log?m)) O ( ( k + m ) log 2 ? n + m 2 ( log ? ? n + log ? m ) ) time after preprocessing P  using O(m2n) O ( m 2 n ) space, where ?>0 ? > 0 is an arbitrarily small constant. We also show that our approach can be applied to the weighted group k-nearest-neighbor query problem and the group k-farthest-neighbor query problem.
segment dragging query k-nearest-neighbor query plane sweep algorithm orthogonal range searching geometric data structure