1
$\begingroup$

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.

$\endgroup$

2 Answers 2

5
$\begingroup$

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.

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.

$\endgroup$
1
  • $\begingroup$ Thanks a lot Joseph. It is exactly I was looking for. Cannot upvote your answer but will soon do it. $\endgroup$
    – user20922
    Jan 27, 2012 at 12:28
1
$\begingroup$

First of all, your problem is ill-posed, since you have to define the 'area occupied by the points' more precisely: Is it the area of their convex hull? Is it the area of the smallest enclosing circle? These are two possible definitions of area, but there may be more.

On the other hand, the problem has all the flavour of an NP-hard problem, though I cannot confirm that yet. If it were so, then basically the only guaranteed algorithm would be exhaustive search in the space of all subsets of $K$ points.

$\endgroup$
3
  • 1
    $\begingroup$ Convex Hull version may be NP-hard, but for many data sets the following should have average case run time in P: Compute the convex hull of the n points, choose two or three vertices, compute the convex hull of the set minus each of those, throw away that point that gives the largest answer, repeat until there are k points left. Even if the result is nonoptimal, it should set the bar pretty high, giving the size of a bounding box that one can use to crawl the space to measure how many points are in each box placement. Gerhard "Ask Me About System Design" Paseman, 2012.01.27 $\endgroup$ Jan 27, 2012 at 10:02
  • $\begingroup$ Thanks a lot Hebert, @Gerhard Paseman for your thoughts. I agree on that question is ill-posed. I have clarified the term "area occupied by them" in the question $\endgroup$
    – user20922
    Jan 27, 2012 at 11:21
  • 1
    $\begingroup$ The definition you give now for the area is precisely the convex hull of the $K$ points. $\endgroup$
    – Hebert
    Jan 27, 2012 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.