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

Suppose I have $N$ points in two dimensional space. I want to know which $K$ of them ($K \lt N$) are located most densely (so that area of Convex Hull of points or sum of squares within cluster is least). How can I find them?

I know K-means-algorithm but it will yield groups that will have number of points different than $K$.

I don't know what should be tags for this question. If someone can tag them appropriately it will be great.

share|cite|improve this question
It's not clear what the question is. You list two alternatives, "so that area occupied by them will be least or sum of squares within cluster is least". These correspond to two different questions. Do you want an answer for both or for either? Regarding the first one, how is the "area occupied by them" defined? – joriki Jan 27 '12 at 11:16
Either of case will do. Area occupied is area of polygon which connects least number points in the group so that all the points in the group are either inside the polygon or are on the boundary of polygon – chatur Jan 27 '12 at 11:25
That polygon is called the convex hull of the points. – joriki Jan 27 '12 at 11:27
@joriki, thanks a lot for the link. I have edited question accordingly. – chatur Jan 27 '12 at 11:30
Are you looking for a theoretically optimal solution or are you trying to implement the algorithm? – user17794 Jan 28 '12 at 20:16

Your Answer


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

Browse other questions tagged or ask your own question.