کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949137 | 1439986 | 2017 | 6 صفحه PDF | دانلود رایگان |
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.
Journal: Computational Geometry - Volume 60, January 2017, Pages 2-7