3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.