Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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, 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.