# 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:

1. The convex hull of a region cannot contain any points from a different region.
2. 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.

-