2026-07-23T04:09:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6866 2024-03-06T10:39:04Z ddc:004 open_access

Most Likely Voronoi Diagrams in Higher Dimensions Kumar, Nirman Raichel, Benjamin Suri, Subhash Verbeek, Kevin Uncertainty Lower bounds Voronoi Diagrams Stochastic 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 Omega(n^{2d}) where n is the number of points. This settles an open question raised in a recent (ISAAC 2014) paper of Suri and Verbeek, 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^{ceil{d/2}}) where the ~O(*) means that logarithmic factors are suppressed. In the worst case, this bound is tight up to polylog factors. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nirman Kumar and Benjamin Raichel and Subhash Suri and Kevin Verbeek 2016 Is Part Of LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2016.31 urn:nbn:de:0030-drops-68667 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.31 eng https://creativecommons.org/licenses/by/3.0/legalcode