New techniques for exact and approximate dynamic closest-point problems

Let S be a set of n points in R(D). It is shown that a range tree can be used to find an L(infinity)-nearest neighbor in S of any query point in O ((log n)(D-1) log log n) time. This data structure has size O (n(log n)(D-1)) and an amortized update time of O ((log n)(D-1) log log n). This result is used to solve the (1 + epsilon)-approximate L(2)-nearest-neighbor problem within the same bounds (up to a constant factor that depends on epsilon and D). In this problem, for any query point p, a point q epsilon S is computed such that the euclidean distance between p and q is at most (1 + epsilon) times the euclidean distance between p and its true nearest neighbor. This is the first dynamic data structure for this problem having close to linear size and polylogarithmic query and update times. New dynamic data structures are given that maintain a closest pair of S. For D greater than or equal to 3, a structure of size O(n) is presented with amortized update time O((log n)(D-1) log log n). The constant factor in this space (resp. time bound) is of the form O(D)(D) (resp. 2(O(D2))). For D = 2 and any nonnegative integer constant k, structures of size O(n log n/(log log n)(k)) (resp. O(n)) are presented that have an amortized update time of O(log n log log n) (resp. O((log n)(2)/(log log n)(k))). Previously, no deterministic linear size data structure having polylogarithmic update time was known for this problem.