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

Given a set of n moving points in Rd, where each point moves along a linear trajectory at arbitrary but constant velocity, we present an O˜(n5/3)-time algorithm1 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˜(n5/3) space and O˜(n2/3) query time, O˜(n5) space and polylogarithmic query time, or O˜(n) space and O˜(n4/5) query time, for any constant ϵ>0 and any constant dimension d.