On the most likely Voronoi diagram and nearest neighbor searching

Let = {(s1,π1), (s2,π2),⋯, (sn,πn)} be a set of stochastic sites, where each site is a tuple (si,πi) consisting of a point si in d-dimensional space and a probability πi of existence. Given a query point q, we define its most likely nearest neighbor (LNN) as the site with the largest probability of being q's nearest neighbor. The Most Likely Voronoi Diagram (LVD) of is a partition of the space into regions with the same LNN. We investigate the complexity of LVD in one dimension and show that it can have size Ω(n2) in the worst-case. We then show that under non-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(nn) under smoothed analysis. We also describe a framework for 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 the worst-case with a bounded number of distinct probabilities. The Pareto-set framework is also applicable to multi-dimensional LNN search via reduction to a sequence of nearest neighbor and spherical range queries