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\leqslant k\leqslant \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\leqslant d_k)\geqslant 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$.