The problem of finding the pair of closest points in a set of points has been a classical example of divide and conquer technique for some decades now. But I could not find any results on finding $k$th closest pair of points; that is the $k$th pair $(p_i, p_j)$ in the list of pairs of distinct points from set $P$, sorted in increasing order of distance.

I could not find anything on that. Do we have any results? More particularly, I am interested in the case of points from a Euclidean plane.

  • 9
    $\begingroup$ Try searching Google scholar for "k closest pairs" — there are things to find there. $\endgroup$ Nov 12, 2014 at 15:58
  • 1
    $\begingroup$ Thanks. Turns out "distance selection" is also a relevant keyword. $\endgroup$
    – Untitled
    Nov 13, 2014 at 18:37


Your Answer

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

Browse other questions tagged or ask your own question.