On the most likely Voronoi diagram and nearest neighbor searching

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

15 Citaten (Scopus)
131 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.
Originele taal-2Engels
TitelAlgorithms and Computation : 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014 : Proceedings
RedacteurenH.K. Ahn, C.S. Shin
Plaats van productieBerlin
ISBN van geprinte versie978-3-319-13074-3
StatusGepubliceerd - 2014
Evenement25th International Symposium on Algorithms and Computation (ISAAC 2014) - Jeonju, Zuid-Korea
Duur: 15 dec 201417 dec 2014
Congresnummer: 25

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743


Congres25th International Symposium on Algorithms and Computation (ISAAC 2014)
Verkorte titelISAAC 2014
Ander25th International Symposium on Algorithms and Computation
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'On the most likely Voronoi diagram and nearest neighbor searching'. Samen vormen ze een unieke vingerafdruk.

Citeer dit