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.