TY - JOUR
ID - 26356
TI - Approximate $k$-nearest neighbor graph on moving points
JO - Transactions on Combinatorics
JA - TOC
LA - en
SN - 2251-8657
AU - Rahmati, Zahed
AD - Department of Mathematics and Computer Science, Amirkabir University of Technology, P.O.Box 15875-4413, Tehran,
Iran.
Y1 - 2023
PY - 2023
VL - 12
IS - 2
SP - 65
EP - 72
KW - approximation
KW - $k$-Nearest Neighbor Graph
KW - Moving Points
DO - 10.22108/toc.2022.130533.1943
N2 - In this paper, we introduce an approximation for the $k$-nearest neighbor graph ($k$-NNG) on a point set $P$ in $\mathbb{R}^d$. For any given $\varepsilon>0$, we construct a graph, that we call the \emph{approximate $k$-NNG}, where the edge with the $i$th smallest length incident to a point $p$ in this graph is within a factor of $(1+\varepsilon)$ of the length of the edge with the $i$th smallest length incident to $p$ in the $k$-NNG. For a set $P$ of $n$ moving points in $\mathbb{R}^d$, where the trajectory of each point $p\in P$ is given by $d$ polynomial functions of constant bounded degree, where each function gives one of the $d$ coordinates of $p$, we compute the number of combinatorial changes to the approximate $k$-NNG, and provide a kinetic data structure (KDS) for maintenance of the edges of the approximate $k$-NNG over time. Our KDS processes $O(kn^2\log^{d+1} n)$ events, each in time $O(\log^{d+1}n)$.
UR - https://toc.ui.ac.ir/article_26356.html
L1 - https://toc.ui.ac.ir/article_26356_e43137e88ed08bf405990ce3538fd339.pdf
ER -