پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 44 |
| تعداد شماره‌ها | 1,473 |
| تعداد مقالات | 12,039 |
| تعداد مشاهده مقاله | 22,306,869 |
| تعداد دریافت فایل اصل مقاله | 9,795,318 |
Approximate $k$-nearest neighbor graph on moving points | ||
| Transactions on Combinatorics | ||
| مقاله 16، دوره 12، شماره 2، شهریور 2023، صفحه 65-72 اصل مقاله (509.62 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22108/toc.2022.130533.1943 | ||
| نویسنده | ||
| Zahed Rahmati* | ||
| Department of Mathematics and Computer Science, Amirkabir University of Technology, P.O.Box 15875-4413, Tehran, Iran. | ||
| چکیده | ||
| 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)$. | ||
| کلیدواژه‌ها | ||
| Approximation؛ $k$-Nearest Neighbor Graph؛ Moving Points | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 227 تعداد دریافت فایل اصل مقاله: 118 |
||