Приближенный поиск $k$-го порядкового расстояния в системе точек единичного квадрата

Для заданных $P=(p_1,\dots,p_n)$ – набора точек единичного квадрата и числа $1\leqslant k\leqslant \binom{n}{2}$ в данной работе рассматривается задача поиска $k$-го порядкового расстояния между элементами $P$ в $\ell_s$-норме, где $s\in\{1,\infty\}$. Иными словами, рассматривается задача поиска такого минимального $d_k$, что выполнено $\sum_{i<j}\mathbb I(\|p_i,p_j\|_s\le d_k)\ge k$, где $\mathbb I$ – индикаторная функция и $s\in\{1,\infty\}$. В настоящей работе для любого $\epsilon>0$ предлагается $\epsilon$-приближенный алгоритм со сложностью $O(n\log n\log(1/\epsilon))$ для вычисления $d_k$.
Библиография: 12 названий.