On the most likely Voronoi diagram and nearest neighbor searching

Let = {(s₁,π₁), (s₂,π₂),⋯, (s_n,π_n)} be a set of stochastic sites, where each site is a tuple (s_i,π_i) consisting of a point s_i 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 Ω(n²) 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.