On the most likely Voronoi diagram and nearest neighbor searching

We consider the problem of nearest-neighbor searching among a set of stochastic sites, where a stochastic site is a tuple (si,pi) consisting of a point si in a d-dimensional space and a probability pi 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 O(n2). We then show that under more natural and less adversarial conditions, the size of the 1-dimensional LVD is significantly smaller: (1) T(kn) if the input has only k distinct probability values, (2) O(nlogn) on average, and (3) O(nnv) 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.