Approximate Search for the $$k$$th Order Distance in a System of Unit Square Points
K. V. Kaimakov, Dmitriy Sergeevich Malyshev · Mathematical Notes · 2024
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 0$$ , we propose an $$\epsilon$$ -approximation algorithm with complexity $$O(n\log n\log(1/\epsilon))$$ for computing $$d_k$$ .