Equal Sized Voronoi Cells minimize mean error/distance Suppose I have $N$ objects $x_1, x_2, ..., x_N$, where $N$ is a large integer number.
Suppose I have $M$ representation points: $y_1, ..., y_M$ where $M < N$.
Consider the quantity $$S = \frac{1}{N} \sum_{i=1}^N d(x_i, \psi(x_i))$$
where $\psi(x_i) $ is equal to $y \in \{y_1, ..., y_M \}$ such that $d(x_i,y) \leq d(x_i, y_k)$ for all $k \in \{1,..., M \}$.
The set of $x_i$'s mapped to a particular $y$ is called its Voronoi cell. Suppose I am trying to minimize $S$ by choosing $y_1, ..., y_M$. Is it true that equal sized, disjoint Voronoi cells is like conducive to minimization?
In a research problem I am working on, I encounter an object like $S$ which I have to lower bound. I find that I can easily give the desired lower bound if I assume equal sized, disjoint Voronoi cells condition. But I want to make sure there's no loss of generality?
 A: There are a number of variations of this problem depending on metrics used and precise details of the objective function. The most common and clearly related formulation is k-means clustering which involves the using the squared Euclidean distance in the objective function you have given (unlike the facility location problems which tend to optimize the maximum distance of any of the points).
For the analogous continuous problem (where rather than summing over $N$ discrete points, the objective integrates over a continuous set), optimal solutions are characterized by centroidal Voronoi tessellations and as the number $M$ of representation points increases, the optimum tend to equal sized hexagons [1].
However, getting a lower bound on your error quantity that you describe is going to require more information about the the $N$ objects you describe. If these points are naturally grouped into $M$ tight clusters, the optimal solution can be arbitrarily small and the sizes of the Voronoi cells are just based on the locations of these clusters which may involve a very non-uniform distribution.
[1] Newman, Donald J., The hexagon theorem, IEEE Trans. Inf. Theory 28, 137-139 (1982). ZBL0476.94006.
