<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-11-12T15:58:23.687Z
Try searching Google scholar for "k closest pairs" — there are things to find there.
David Eppstein
CC BY-SA 3.0
2014-11-13T18:37:21.957Z
Thanks. Turns out "distance selection" is also a relevant keyword.
Untitled
<cg.comp-geom>
$k$th closest pair of points
Untitled
# $k$th closest pair of points

(Asked by: username_0 on 2014-11-12)

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.

**Tags:** cg.comp-geom

> **Comments:**
> **username_1**: Try searching Google scholar for "k closest pairs" — there are things to find there.  
> **username_0**: Thanks. Turns out "distance selection" is also a relevant keyword.  

---

## 0 answers

