We consider the problem of nearest-neighbor searching among a set of stochastic sites, where a stochastic site is a tuple (s_i, π_i) consisting of a point s_i in a d-dimensional space and a probability π_i, determining its existence. The problem is interesting and non-trivial even in 1-dimension, where the Most Likely Voronoi Diagram (LVD) is shown to have worst-case complexity Ω(n~2). We then show that under more natural and less adversarial conditions, the size of the 1-dimensional LVD is significantly smaller: (1) θ(kn) if the input has only k distinct probability values, (2) O(n log n) on average, and (3) O(n n~(1/2)) under smoothed analysis. We also present an alternative approach to the most likely nearest neighbor (LNN) search using Pareto sets, which gives a linear-space data structure and sub-linear query time in 1D for average and smoothed analysis models, as well as worst-case with a bounded number of distinct probabilities. Using the Pareto-set approach, we can also reduce the multi-dimensional LNN search to a sequence of nearest neighbor and spherical range queries.
展开▼
