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 [12]. 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.