I am working on an algorithm for which bounds on the size of voronoi cells will come in handy.
Suppose that the domain $D$ is partitioned according to the Voronoi cells $D_1,\dots,D_n$ with Voronoi seeds/centers/generators $x_1,\dots,x_n$.
Are there any existing results about upper bounds for $ \displaystyle \int |x-x_k|^2 \,dx$ as a function of $n$, the number of centers? Here, $k \in [1,n]$ and $|\cdot|$ is the Euclidean norm.
Are such results available as well if my domain $D$ is equipped with a distribution, i.e. $ \displaystyle \int |x-x_k|^2 \,dF(x)$?
Without some additional restrictions on how the Voronoi generators are constructed, there isn't going to be a very useful bound. Consider a 2D square domain and generators that are all in a single line. For $n$ generators in this case,
$$ \int_{V_k} |x-x_k|^2 dx \approx \frac{1}{12n} $$
So $\sum_{k=1}^n \int_{V_k} |x-x_k|^2$ does not approach $0$ like it would for a "normal" Voronoi diagram where the diameter of the cells gets smaller as the number of generators increases.