I have come across some problem. I have been given N points , from which I have to select K points. Each points is having some distance from the origin. say there are 5 points with distance from origin 10, 15,20,25,30. I have to select three of them so that minimum distance between them is maximized. So here I will select 10, 20, 30. What can be the possible approach to this problem?
See the answer to this more general question. Given a min distance d, you can determine whether you can choose such a subset in O(N). Using this test you can binary search to find the maximum such distance. I believe this gives you O(N log D) where D is the distance between the first and last points (and therefore the upper bound). For the version of the problem I saw with N=10^5 and D=10^9 this solution was fine.