Incremental 2-D Nearest-Point Search with Evenly Populated Strips
Abstract
The incremental nearest-point search successively inserts query points into the space partition data structure, and the nearest point for each of them is simultaneously found among the previously inserted ones. The paper introduces a new approach which solves this task in 2-D space in a nearly optimal manner. The proposed dynamic partition into parallel strips, each containing a limited number of points structured in the deterministic skip list, successfully prevents situations with over-populated strips, while its further advanced version with two perpendicular partitions and four categories of deterministic skip lists efficiently decreases the number of strips to be examined in a great majority of practical cases.
Full Text:
PDFReferences
F. Aurenhammer F. (1991). Voronoi diagrams – a survey of a fundamental geometric data structure, ACM Computing Surveys, ACM, vol. 23, iss. 3, pp. 345-405.
Chan T. M.; Rahmati Z. (2017). Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points. Computational Geometry, Elsevier Science, vol. 60, Jan. 2017, pp. 2-7.
Chaurasia V.; Chaurasia V. (2016). Statistical feature extraction based technique for fast fractal image compression. Journal of Visual Communication and Image Representation, Elsevier Science, vol. 41, Nov. 2016, pp. 87-95.
Cleary J. G. (1979). Analysis of an Algorithm for Finding Nearest Neighbors in Euclidean Space. ACM Transactions on Mathematical Software, ACM, vol. 5, iss. 2, pp. 183-192.
Cormen T. H.; Leiserson C. E.; Rivest R. L.; Stein C. (2001). Introduction to Algorithms, 2nd Edition, MIT Press and McGraw-Hill.
de Gomensoro Malheiros M.; Walter M. (2016). Spatial sorting: an efficient strategy for approximate nearest neighbor searching. Computers & Graphics, Elsevier Science, vol. 57, June 2016, pp. 112-126.
Gómez-Ballester E.; Micó L.; Oncina J. (2006). Some approaches to improve tree-based nearest neighbour search algorithms. Pattern Recognition, Elsevier Science, vol. 39, iss. 2, pp. 171-179.
Guibas L. J.; Knuth D. E.; Sharir M. (1992). Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica, Springer, vol. 7, iss. 4, pp. 381-413.
Han Y.; Tang J.; Zhou Z.; Xiao M.; Sun L.; Wang Q. (2014). Novel itinerary-based KNN query algorithm leveraging grid division routing in wireless sensor networks of skewness distribution. Personal and Ubiquitous Computing, Springer, vol. 18, iss. 8, pp. 1989-2001.
Kanda T.; Sugihara K. (2002). Comparison of various trees for nearest-point search with/without the Voronoi diagram. Information Processing Letters, Elsevier Science, vol. 84, iss. 1, pp. 17-22.
Kirkpatrick, D. G. (1983). Optimal search in planar subdivisions, SIAM J. Comput., vol 12, iss. 1, pp. 28-35.
Long Y.; Zhu F.; Shao L. (2016). Recognising occluded multi-view actions using local nearest neighbour embedding. Computer Vision and Image Understanding, Elsevier Science, vol. 144, March 2016, pp. 36-45.
Munro J. I.; Papadakis T.; Sedgewick R. (1992). Deterministic skip lists. Proceedings of the Third ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Orlando, USA, pp. 367-375.
Nagasue J.; Konishi Y; Araki N.; Sato T.; Ishigaki H. (2009). Slope-Walking of a Biped Robot with K Nearest Neighbor Method. Proceedings of the 2009 Fourth International Conference on Innovative Computing, Information and Control, IEEE Computer Society, Kaohsiung, Taiwan, pp. 173-176.
Pugh W. (1990). Skip lists: A probabilistic alternative to balanced trees. Communications of the ACM, ACM, vol. 33, iss. 6, pp. 668-676.
Savchenko A. V. (2017). Maximum-likelihood approximate nearest neighbor method in real-time image recognition. Pattern Recognition, Elsevier, vol. 61, Jan. 2017, pp. 459-469.
Wang. H.; Cao J.; Shu L.; Rafiei D. (2013). Locality sensitive hashing revisited: filling the gap between theory and algorithm analysis. Proceedings of the 22nd ACM international conference on Information & Knowledge Management, ACM, San Francisco, USA, pp. 1969-1978.
Wei-Kleiner F. (2016). Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs. Journal of Computer and System Sciences, Elsevier Science, vol. 82, iss. 1, part A, pp. 23–44.
Zadravec M.; Brodnik A.; Mannila M.; Wanne M.; Žalik B. (2008). A practical approach to the 2D incremental nearest-point problem suitable for different point distributions. Pattern Recognition, Elsevier Science, vol. 41, iss. 2, pp. 646-653.
Zadravec M.; Žalik B. (2005). An almost distribution-independent incremental Delaunay triangulation algorithm. Visual Computer, Springer, vol. 21, iss. 6, pp. 384-396.
Zheng R. Y. (2010). Machine Learning Approaches to Bioinformatics, World Scientific Publishing Co., Inc.
DOI: https://doi.org/10.31449/inf.v43i1.2679
This work is licensed under a Creative Commons Attribution 3.0 License.