On the most likely Voronoi diagram and nearest neighbor searching

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

15 Citations (Scopus)
138 Downloads (Pure)


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.
Original languageEnglish
Title of host publicationAlgorithms and Computation : 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014 : Proceedings
EditorsH.K. Ahn, C.S. Shin
Place of PublicationBerlin
ISBN (Print)978-3-319-13074-3
Publication statusPublished - 2014
Event25th International Symposium on Algorithms and Computation (ISAAC 2014) - Jeonju, Korea, Republic of
Duration: 15 Dec 201417 Dec 2014
Conference number: 25

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Conference25th International Symposium on Algorithms and Computation (ISAAC 2014)
Abbreviated titleISAAC 2014
CountryKorea, Republic of
Internet address


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

Cite this