On the most likely Voronoi diagram and nearest neighbor searching

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)
284 Downloads (Pure)

Abstract

Let = {(s11), (s22),⋯, (snn)} be a set of stochastic sites, where each site is a tuple (sii) 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.

Original languageEnglish
Pages (from-to)151-166
Number of pages16
JournalInternational Journal of Computational Geometry and Applications
Volume26
Issue number3-4
DOIs
Publication statusPublished - 1 Dec 2016

Keywords

  • geometric data structures
  • nearest neighbors
  • Pareto sets
  • Uncertain data
  • Voronoi diagram

Fingerprint

Dive into the research topics of 'On the most likely Voronoi diagram and nearest neighbor searching'. Together they form a unique fingerprint.

Cite this