We propose a self-improving algorithm for computing Voronoi diagrams under a\ngiven convex distance function with constant description complexity. The $n$\ninput points are drawn from a hidden mixture of product distributions; we are\nonly given an upper bound $m = o(\\sqrt{n})$ on the number of distributions in\nthe mixture, and the property that for each distribution, an input instance is\ndrawn from it with a probability of $\\Omega(1/n)$. For any $\\varepsilon \\in\n(0,1)$, after spending $O\\bigl(mn\\log^{O(1)} (mn) + m^{\\varepsilon}\nn^{1+\\varepsilon}\\log(mn)\\bigr)$ time in a training phase, our algorithm\nachieves an $O\\bigl(\\frac{1}{\\varepsilon}n\\log m +\n\\frac{1}{\\varepsilon}n2^{O(\\log^* n)} + \\frac{1}{\\varepsilon}H\\bigr)$ expected\nrunning time with probability at least $1 - O(1/n)$, where $H$ is the entropy\nof the distribution of the Voronoi diagram output. The expectation is taken\nover the input distribution and the randomized decisions of the algorithm. For\nthe Euclidean metric, the expected running time improves to\n$O\\bigl(\\frac{1}{\\varepsilon}n\\log m + \\frac{1}{\\varepsilon}H\\bigr)$.\n