Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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.

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