2026-07-24T06:33:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15441 2024-03-06T10:55:17Z ddc:004 open_access

Self-Improving Voronoi Construction for a Hidden Mixture of Product Distributions Cheng, Siu-Wing Wong, Man Ting entropy Voronoi diagram convex distance function hidden mixture of product distributions We propose a self-improving algorithm for computing Voronoi diagrams under a given convex distance function with constant description complexity. The n input points are drawn from a hidden mixture of product distributions; we are only given an upper bound m = o(√n) on the number of distributions in the mixture, and the property that for each distribution, an input instance is drawn from it with a probability of Ω(1/n). For any ε ∈ (0,1), after spending O(mn log^O(1)(mn) + m^ε n^(1+ε) log(mn)) time in a training phase, our algorithm achieves an O(1/ε n log m + 1/ε n 2^O(log^* n) + 1/ε H) expected running time with probability at least 1 - O(1/n), where H is the entropy of the distribution of the Voronoi diagram output. The expectation is taken over the input distribution and the randomized decisions of the algorithm. For the Euclidean metric, the expected running time improves to O(1/ε n log m + 1/ε H). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Siu-Wing Cheng and Man Ting Wong 2021 Is Part Of LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2021.8 urn:nbn:de:0030-drops-154418 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.8 eng https://creativecommons.org/licenses/by/4.0/legalcode