Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points
Timothy M. Chan, Zahed Rahmati · Canadian Conference on Computational Geometry · 2015
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 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 ź ( n 5 / 3 ) space and O ź ( n 2 / 3 ) query time, O ź ( n 5 ) 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. 1The notation O ź is used to hide polylogarithmic factors. That is, O ź ( f ( n ) ) = O ( f ( n ) log c ź n ) , where c is a constant.