# Find most densely located $K$ points among $N$ ($N \gt K$) points in two dimension

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.

-
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