Closest pair and the post office problem for stochastic points (Q390124)

The paper deals with the study of a stochastic version of the post office problem. In the considered problem we have a set of \(n\) points \(M\) in a \(d\)-dimensional Euclidean space. Each member \(m_i\) of \(M\) has probability \(p_i\) of being present and probability \(1 - p_i\) of being absent. The authors show that it is \#P-hard to compute the probability that the closest pair of points has distance at most a value \(l\), even for dimension \(2\) under the \(L_{\infty}\) norm. Next, they show that in the linearly-separable and bichromatic planar case the probability can be computed in polynomial time under the \(L_{\infty}\) norm. Moreover, the authors prove that without the linear separability, even the bichromatic version of the problem is \#P-hard under the \(L_2\) or \(L_{\infty}\) norm, and with linear separability and \(L_{\infty}\) norm the bichromatic case become \#P-hard in dimension \(d \geq 3\). Finally, they give a linear-space data structure with \(O(\log n)\) query time to compute the expected distance of a given query point to its \((1 + \varepsilon)\)-approximate nearest neighbour when the dimension \(d\) is a constant.