Self-Improving Voronoi Construction for a Hidden Mixture of Product Distributions

Siu-Wing Cheng, Man Ting Wong

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 fro…