Choose the closest k points from given n points

algorithm language-agnostic geometry computational-geometry
pathikrit picture pathikrit · Mar 30, 2011 · Viewed 8.1k times · Source

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

dcn picture dcn · Mar 31, 2011

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 :-)

Related questions

How to check if line segment intersects a rectangle?

If you have 2 points, (x1, y1) and (x2, y2), which represent two opposite corners of a rectangle, and 2 other points, (x3,y3) and (x4,y4), which represent 2 endpoints of a line segment, how can you check if the line segment …

Read More
Equation for testing if a point is inside a circle

If you have a circle with center (center_x, center_y) and radius radius, how do you test if a given point with coordinates (x, y) is inside the circle?

Read More
How to find two most distant points?

This is a question that I was asked on a job interview some time ago. And I still can't figure out sensible answer. Question is: you are given set of points (x,y). Find 2 most distant points. Distant from each …

Read More