Group nearest-neighbor queries in the L1L1 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 L1L1 plane. More precisely, a query is assigned with a set Q of at most m points and a positive integer k   with k≤nk≤n, and the distance between a point p of P and a query set Q   is defined as the sum of L1L1 distances from p   to all q∈Qq∈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(Tminlog⁡n+(k+m2)(log⁡log⁡n+log⁡m)) time after preprocessing P   using O(m2nlog2⁡n)O(m2nlog2⁡n) space, where Tmin=min⁡{k+m,m2}Tmin=min⁡{k+m,m2}, or (2) a group k  -NN query can be handled in O((k+m)log2⁡n+m2(logϵ⁡n+log⁡m))O((k+m)log2⁡n+m2(logϵ⁡n+log⁡m)) time after preprocessing P   using O(m2n)O(m2n) 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.