Choose the closest k points from given n points

Question

You are given a set U of n points on the plane and you can compute distance between any pair of points in constant time. Choose a subset of U called C such that C has exactly k points in it and the distance between the farthest 2 points in C is as small as possible for given k. 1 < k <= n

What's the fastest way to do this besides the obvious n-choose-k solution?

Answer 1

A solution is shown in Finding k points with minimum diameter and related problems - Aggarwal, 1991. The algorithm described therein has running time: O(k^2.5 n log k + n log n)

For those who have no access to the paper: the problem is called k-diameter and definied as

Find a set of k points with minimum diameter. The diameter of a set is the maximum distance between any points of the set.

I cannot really give an overview over the presented algorithm, but it includes computing the (3k - 3)th order Voronoi diagram of the points, and then solve the problem for each of the O(kn) Voronoi sets (by computing maximum independent sets in some bipartite graphs)... I guess that I am trying to say is, that it is highly non-trivial, and far beyond both an interview and this site :-)

Answer 2

Since this is an interview question, here is my shot at a solution. (As dcn points out below, this is not guaranteed to return the optimal solution, though it should still be a decent heuristic. Good catch, dcn!)

1. Create a set S_p with a single point P.
2. Compute the distance between every point in S_p and every point outside of it, then add the point with the smallest max distance to S_p.
3. Repeat 2. until S_p has k points.
4. Repeat 1-3 using each point once as the initial P. Take the S_p which has the smallest max distance.

There are O(k) points in S_p, and O(n) points outside of it, so finding the point with the smallest max distance is O(nk). We repeat this k times, then repeat the whole procedure n times, for an overall complexity of O(n²k²).

We can improve on this by caching the max distance between any point in S_p and each point outside of S_p. If maxDistanceFromPointInS[pointOutsideS] is, say, an O(1) hash-table containing the current max distance between every point pointOutsideS and some point inside S_p, then every time we add a new point newPoint, we set maxDistanceFromPointInS[p] = Max(maxDistanceFromPointInS[p], distance(newPoint, p)) for all points p outside of S_p. Then finding the smallest max distance is O(n), adding a point to S_p is O(n). Repeating this k times gives us O((n+n)k) = O(nk). Finally, we repeat the whole procedure n times, for an overall complexity of O(n²k).

We could improve finding the smallest max distance to O(1) using a heap, but that would not change the overall complexity.

---

By the way, it took an hour to write this all up - there's no way I could have done this in an interview.