2
$\begingroup$

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.

  • 0
    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?2012-01-27
  • 0
    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 polygon2012-01-27
  • 0
    That polygon is called the [convex hull](http://en.wikipedia.org/wiki/Convex_hull#Convex_hull_of_a_finite_point_set) of the points.2012-01-27
  • 0
    @joriki, thanks a lot for the link. I have edited question accordingly.2012-01-27
  • 0
    Are you looking for a theoretically optimal solution or are you trying to implement the algorithm?2012-01-28

0 Answers 0