Approximate $k$-nearest neighbor graph on moving points

Document Type : Research Paper

Author

Department of Mathematics and Computer Science, Amirkabir University of Technology, P.O.Box 15875-4413, Tehran, Iran.

Abstract

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)$.

Keywords

Main Subjects

References

[1] Z. Rahmati, Simple, faster kinetic data structures, PhD. Thesis, University of Victoria (2014).
[2] M. Abam, New Data Structures and Algorithms for Mobile Data, PhD. Thesis, Eindhoven University of Technology,
(2007).
[3] D. Russel, Kinetic Data Structures in Practice, PhD. Thesis, Stanford University, (2007).
[4] J. Basch, Kinetic Data Structures, PhD. Thesis, Stanford University, (1999).
[5] Z. Rahmati, V. King and S. Whitesides, Kinetic Data Structures for All Nearest Neighbors and Closest Pair in the
Plane, in: Proceedings of the 29th annual symposium on Symposuim on computational geometry (SoCG ’13), (2013)
137–144.
[6] M. Abam, Z. Rahmati and A. Zarei, Kinetic Pie Delaunay Graph and its Applications, in: Proceedings of the 13th
Scandinavian Symposium and Workshops on Algorithms Theory (SWAT ’12), (2012) 48–58.
[7] Z. Rahmati, M. Abam, V. King and S. Whitesides, Kinetic data structures for the Semi-Yao graph and all nearest
neighbors in Rd , in: Proceedings of the 26th Canadian Conference on Computational Geometry (CCCG ’14), (2014)
2–10.
[8] Z. Rahmati, M. A. Abam, V. King, S. Whitesides and A. Zarei, A simple, faster method for kinetic proximity
problems, Comput. Geom., 48 (2015) 342–359.
[9] J. Basch, L. J. Guibas and J. Hershberger, Data structures for mobile data, in: Proceedings of the 8th Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA ’97), Society for Industrial and Applied Mathematics,
Philadelphia, PA, USA, 1997, 747–756.
[10] P. M. Vaidya, An O(n log n) algorithm for the all-nearest-neighbors problem, Discrete Comput. Geom., 4 (1989)
101–115.
[11] M. T. Dickerson and D. Eppstein, Algorithms for proximity problems in higher dimensions, Comput. Geom, 5 (1996)
277–291.
[12] P. B. Callahan and S. R. Kosaraju, A decomposition of multidimensional point sets with applications to k-nearest-
neighbors and n-body potential fields, J. Assoc. Comput. Mach., 42 (1995) 67–90.
[13] K. L. Clarkson, Fast algorithms for the all nearest neighbors problem, in: Proceedings of the 24th Annual Symposium
on Foundations of Computer Science (FOCS ’83), IEEE Computer Society, Washington, DC, USA, (1983) 226–232.
[14] J. Basch, L. J. Guibas and L. Zhang, Proximity problems on moving points, in: Proceedings of the 13th Annual
Symposium on Computational Geometry (SoCG ’97), ACM, New York, NY, USA, (1997) 344–351.
[15] P. K. Agarwal, H. Kaplan, M. Sharir, Kinetic and dynamic data structures for closest pair and all nearest neighbors,
ACM Trans. Algorithms, 5 (2009) 37 pp.
[16] T. M. Chan and Z. Rahmati, Approximating the minimum closest pair distance and nearest neighbor distances of
linearly moving points, in: Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG ’15),
(2015) 136–140.
[17] Z. Rahmati, M. Abam, V. King and S. Whitesides, Kinetic k-Semi-Yao graph and its applications, Comput. Geom.,
77 (2019) 10–26.
[18] M. A. Abam and M. de Berg, Kinetic spanners in Rd , Discrete Comput. Geom., 45 (2011) 723–736.
[19] M. d. Berg, O. Cheong, M. v. Kreveld and M. Overmars, Computational Geometry: Algorithms and Applications,
3rd Edition, Springer-Verlag TELOS, Santa Clara, CA, USA, 2008.
[20] S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman and A. Y. Wu, An optimal algorithm for approximate nearest
neighbor searching in fixed dimensions, Journal of the ACM 45 (6) (1998) 891–923.
[21] M. Connor, P. Kumar, Fast construction of k-nearest neighbor graphs for point clouds, IEEE Transactions on
Visualization and Computer Graphics, 16 (2010) 599–608.
[22] P. K. Agarwal, B. Aronov, T. M. Chan and M. Sharir, On levels in arrangements of lines, segments, planes, and
triangles, Discrete Comput. Geom., 19 (1998) 315–331.
[23] T. M. Chan, On levels in arrangements of curves, ii: A simple inequality and its consequences, Discrete Comput.
Geom., 34 (2005) 11–24.
[24] T. M. Chan, On levels in arrangements of curves, iii: further improvements, in: Proceedings of the 24th annual
Symposium on Computational Geometry (SoCG ’08), ACM, New York, NY, USA, (2008) 85–93.
[25] M. Sharir, On k-sets in arrangements of curves and surfaces, Discrete Comput. Geom., 6 (1991) 593–613.

Files

History

  • Receive Date: 04 December 2021
  • Revise Date: 12 February 2022
  • Accept Date: 19 February 2022
  • Published Online: 01 June 2023

Share

How to cite

Statistics