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$$ .