کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414287 | 680876 | 2014 | 10 صفحه PDF | دانلود رایگان |
Given a (master) set M of n points in d -dimensional Euclidean space, consider drawing a random subset that includes each point mi∈Mmi∈M with an independent probability pipi. How difficult is it to compute elementary statistics about the closest pair of points in such a subset? For instance, what is the probability that the distance between the closest pair of points in the random subset is no more than ℓ, for a given value ℓ? Or, can we preprocess the master set M such that given a query point q, we can efficiently estimate the expected distance from q to its nearest neighbor in the random subset? These basic computational geometry problems, whose complexity is quite well-understood in the deterministic setting, prove to be surprisingly hard in our stochastic setting. We obtain hardness results and approximation algorithms for stochastic problems of this kind.
Journal: Computational Geometry - Volume 47, Issue 2, Part B, February 2014, Pages 214–223