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

Математические заметки. 2024. Т. 116. № 4. С. 504–509.

Каймаков К. В., Малышев Д. С.

Для заданных $P=(p_1,\ldots,p_n)$ --- набора точек единичного квадрата и числа $1\leq k\leq \binom{n}{2}$ в данной работе рассматривается задача поиска $k$-ого порядкового расстояния между элементами $P$ в $l_s$-норме, где $s\in \{1,\infty\}$. Иными словами, рассматривается задача поиска такого минимального $d_k$, что выполнено $\sum\limits_{i<j}\indicator(\|p_i,p_j\|_{s} \leq d_k)\geq k$, где $\indicator$ --- индикаторная функция и $s\in \{1,\infty\}$. В настоящей работе для любого $\epsilon>0$ предлагается $\epsilon$-приближенный алгоритм со сложностью $O(n\log(n)\log(\frac{1}{\epsilon}))$ для вычисления $d_k$.  

Ключевые слова: эффективный алгоритм, вычислительная геометрия, поиск порядковых расстояний