Advertisement
Published in:
2011 | OriginalPaper | Chapter
Closest Pair and the Post Office Problem for Stochastic Points
Authors : Pegah Kamousi, Timothy M. Chan, Subhash Suri
Published in: Algorithms and Data Structures
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Given a (master) set
M
of
n
points in
d
-dimensional Euclidean space, consider drawing a random subset that includes each point
m
i
∈
M
with an independent probability
p
i
. 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? We obtain hardness results and approximation algorithms for stochastic problems of this kind.