@inproceedings{2fa1fa84e7264c9db867790a98fc8067,
title = "Most likely Voronoi diagrams in higher dimensions",
abstract = "The Most Likely Voronoi Diagram is a generalization of the well known Voronoi Diagrams to a stochastic setting, where a stochastic point is a point associated with a given probability of existence, and the cell for such a point is the set of points which would classify the given point as its most likely nearest neighbor. We investigate the complexity of this subdivision of space in d dimensions. We show that in the general case, the complexity of such a subdivision is Ω(n2d) where n is the number of points. This settles an open question raised in a recent (ISAAC 2014) paper of Suri and Verbeek [24], which first defined the Most Likely Voronoi Diagram. We also show that when the probabilities are assigned using a random permutation of a fixed set of values, in expectation the complexity is only {\~O}(n⌈d/2⌉) where the {\~O}(•) means that logarithmic factors are suppressed. In the worst case, this bound is tight up to polylog factors.",
keywords = "Lower bounds, Stochastic, Uncertainty, Voronoi diagrams",
author = "N. Kumar and B. Raichel and S. Suri and K.A.B. Verbeek",
year = "2016",
month = dec,
day = "1",
doi = "10.4230/LIPIcs.FSTTCS.2016.31",
language = "English",
series = "Leibniz International Proceedings in Informatics",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",
pages = "31.1--31.14",
editor = "A. Lal and S. Akshay and S. Saurabh and S. Sen",
booktitle = "36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016",
note = "36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016 ; Conference date: 13-12-2016 Through 15-12-2016",
}