Approximate Search for the \(k\)th Order Distance in a System of Unit Square Points

For a given tuple \(P=(p_1,\dots,p_n)\) (a set of points of the unit square) and a number \(1\le k\le \binom{n}{2}\) , this paper considers the problem of finding the \(k\) th ordinal distance between elements of \(P\) in the \(\ell_s\) -norm, where \(s\in\{1,\infty\}\) . In other words, we consider the problem of finding a minimal \(d_k\) such that \(\sum_{i<j}\mathbb I(\|p_i,p_j\|_s\le d_k)\ge k\) , where \(\mathbb I\) is the indicator function and \(s\in\{1,\infty\}\) . In this paper, for any \(\epsilon>0\) , we propose an \(\epsilon\) -approximation algorithm with complexity \(O(n\log n\log(1/\epsilon))\) for computing \(d_k\) .