Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points

Given a set of n moving points in R^d, where each point moves along a linear trajectory at arbitrary but constant velocity, we present an O˜(n^5/3)-time algorithm¹ to compute a (1+ϵ)-factor approximation to the minimum closest pair distance over time, for any constant ϵ>0 and any constant dimension d. This addresses an open problem posed by Gupta, Janardan, and Smid [1]. More generally, we consider a data structure version of the problem: for any linearly moving query point q, we want a (1+ϵ)-factor approximation to the minimum nearest neighbor distance to q over time. We present a data structure that requires O˜(n^5/3) space and O˜(n^2/3) query time, O˜(n⁵) space and polylogarithmic query time, or O˜(n) space and O˜(n^4/5) query time, for any constant ϵ>0 and any constant dimension d. The notation O˜ is used to hide polylogarithmic factors. That is, O˜(f(n))=O(f(n)log^c⁡n), where c is a constant.