Suppose I have N points in two dimensional space. 


I want to know which K of them are located most densely (so that area occupied by them will be least or sum of squares within cluster is least). 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. How can I find them?


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



Find most densely located K points among N (N>K) points in two dimension
Under the natural interpretation that the area of the convex hull of $k$ points is to be minimized,
the
question was addressed in David Eppstein's 1992 paper, "New algorithms for minimum area $k$-gons,"
[In *Proceedings 3rd ACM-SIAM Symposium on Discrete algorithms* (SODA '92), 83-88](http://dl.acm.org/citation.cfm?id=139422). 



> 
> We also solve the related problem of finding a set of $k$ points with minimum area convex hull
>  [among $n$ points in the plane], in time $O(n^2 \log n + k^3 n^2)$.
> 
> 
> 


I think the definition using "connects least number points" is in fact the convex hull.


