Aggregate-Max Nearest Neighbor Searching in the Plane

Original · EN

We study the aggregate/group nearest neighbor searching for the MAX operator in the plane. For a set P of n points and a query set Q of m points, the query asks for a point of P whose maximum distance to the points in Q is minimized. We present data structures for answering such queries for both L₁ and L₂ distance measures. Previously, only heuristic and approximation algorithms were given for both versions. For the L₁ version, we build a data structure of O(n) size in O(n n) time, such that each query can be answered in O(m+ n) time. For the L₂ version, we build a data structure in O(n n) time and O(n n) space, such that each query can be answered in O(m√nᵒ⁽¹⁾ n) time, and alternatively, we build a data structure in O(n²⁺ε) time and space for any ε>0, such that each query can be answered in O(m n) time. Further, we extend our result for the L₁ version to the top-k queries where each query asks for the k points of P whose maximum distances to Q are the smallest for any k with 1≤ k≤ n: We build a data structure of O(n) size in O(n n) time, such that each top-k query can be answered in O(m+k n) time.