Partitioning Points Into Regions I have a list of points $p_1, p_2, ..., p_n$ in the plane where each point has a weight $w(p)$ and I want to partition the points into $k$ separate regions with the following constraints:


The convex hull of a region cannot contain any points from a different region.
Let $R_1, R_2, ..., R_k$ be the resulting regions. Let $$W(R_i) = \sum\limits_{p\in R_i} w(p)$$


Then, I wish to minimize the standard deviation of $\left\{{W(R_1), W(R_2), ..., W(R_k)}\right\}$ (So all regions should contain as close to the same total weight as possible.)

Does anyone know of any good algorithms that would allow me to compute $R_1, R_2, ..., R_k$? An optimal solution is not necessary for this problem. Also, n  ~ 10000 and k ~ 20. It seems like some sort of modified k-means clustering should work. Thanks in advance.
There is a growing literature in the area of computational geometry which deals with issues related to partitioning point sets into groups of approximately uniform size for some "secondary goal." This paper, http://cccg.ca/proceedings/2007/03a1.pdf while not directly dealing with your question may give you some useful ideas as well as having references to other approaches to point partition questions that have been developed by William Steiger (Rutgers) and others.
The methods described in this paper https://arxiv.org/pdf/1710.03358.pdf are sufficient for meeting the criteria posed in the original question.

The key to generating the desired region is given by the use of power diagrams, which assign points to centers based on the weighted squared distance measure. Then, this modification is paired with an iterative process to generate Voronoi cells, giving the final result. The authors also describe an optimization based on a min cost flow algorithm