Geodesic
Approximate search for the $k$th order distance in a system of unit square points
Matematičeskie zametki, Tome 116 (2024) no. 4, pp. 504-509 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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, 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$.
Keywords: computational geometry, search for ordinal distances
Mots-clés : efficient algorithm. 
@article{MZM_2024_116_4_a1,
     author = {K. Kaymakov and D. S. Malyshev},
     title = {Approximate search for the $k$th order distance in a~system of unit square points},
     journal = {Matemati\v{c}eskie zametki},
     pages = {504--509},
     year = {2024},
     volume = {116},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2024_116_4_a1/}
}
TY  - JOUR
AU  - K. Kaymakov
AU  - D. S. Malyshev
TI  - Approximate search for the $k$th order distance in a system of unit square points
JO  - Matematičeskie zametki
PY  - 2024
SP  - 504
EP  - 509
VL  - 116
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/MZM_2024_116_4_a1/
LA  - ru
ID  - MZM_2024_116_4_a1
ER  - 
%0 Journal Article
%A K. Kaymakov
%A D. S. Malyshev
%T Approximate search for the $k$th order distance in a system of unit square points
%J Matematičeskie zametki
%D 2024
%P 504-509
%V 116
%N 4
%U http://geodesic.mathdoc.fr/item/MZM_2024_116_4_a1/
%G ru
%F MZM_2024_116_4_a1
K. Kaymakov; D. S. Malyshev. Approximate search for the $k$th order distance in a system of unit square points. Matematičeskie zametki, Tome 116 (2024) no. 4, pp. 504-509. http://geodesic.mathdoc.fr/item/MZM_2024_116_4_a1/

[1] K. L. Clarkson, “Fast algorithms for the all nearest neighbors problem”, Proceedings of 24th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, 1983, 226–232

[2] S. Fortune, J. E. Hopcroft, “A note on Rabin's nearest-neighbor algorithm”, Information Processing Letters, 8:1 (1979), 20–23 | DOI | MR

[3] S. Khuller, Y. Matias, “A simple randomized sieve algorithm for the closest-pair problem”, Information and Computation, 118:1 (1995), 34–37 | DOI | MR

[4] S. N. Bespamyatnikh, “An optimal algorithm for closest-pair maintenance”, Discrete and Computational Geometry, 19 (1998), 175–195 | DOI | MR

[5] H.-P. Lenhof, M. Smid, “Enumerating the $k$ closest pairs optimally”, Proceedings of 33rd Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, 1992, 380–386

[6] H.-P. Lenhof, M. Smid, “Sequential and parallel algorithms for the $k$ closest pairs problem”, International Journal of Computational Geometry and Applications, 5:3 (1995), 273–285 | DOI | MR

[7] H. Kurasawa, A. Takasu, J. Adachi, “Finding the $k$-closest pairs in metric spaces”, Proceedings of the 1st Workshop on New Trends in Similarity Search, Association for Computing Machinery, New York, 2011, 8–13

[8] A. Corall, A. Manolopoulos, Y. Theodoridis, M. Vassilakopoulos, “Closest pair queries in spatial databases”, ACM SIGMOD Record, 29:2 (2000), 189–200 | DOI

[9] M. Aumüller, M. Ceccarello, “Solving $k$-closest pairs in high-dimensional data”, Similarity Search and Applications, Springer, Berlin, 2023, 200–214

[10] J. L. Bentley, T. A. Ottman, “Algorithms for reporting and counting geometric intersections”, IEEE Transactions on Computers, C-28:9 (1979), 643–647 | DOI

[11] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, The MIT Press, Cambridge, Massachusetts London, England, 2022 | MR

[12] P. M. Fenwick, “A new data structure for cumulative frequency tables”, Software: Practice and Experience, 24:3 (1994), 327–336 | DOI