Incremental 2-D Nearest-Point Search with Evenly Populated Strips

Authors

  • David Podgorelec University of Maribor, Faculty of Electrical Engineering and Computer Science
  • Denis Špelič Impol 2000, d. d. Partizanska 38, 2310 Slovenska Bistrica

DOI:

https://doi.org/10.31449/inf.v43i1.2679

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.

Author Biographies

David Podgorelec, University of Maribor, Faculty of Electrical Engineering and Computer Science

Research Fellow in the Laboratory for Geometric Modelling and Multimedia Algorithms

Denis Špelič, Impol 2000, d. d. Partizanska 38, 2310 Slovenska Bistrica

Used to work at the University of Maribor,Faculty of Electrical Engineering and Computer Science till April 2018 (also when the paper was written), but then moved to Impol 2000, d.d.

References

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.

Downloads

Published

2019-03-01

How to Cite

Podgorelec, D., & Špelič, D. (2019). Incremental 2-D Nearest-Point Search with Evenly Populated Strips. Informatica, 43(1). https://doi.org/10.31449/inf.v43i1.2679

Issue

Vol. 43 No. 1 (2019)

Section

Middle-European Conference on Applied Theoretical Computer Science (MATCOS-16)

License

I assign to Informatica, An International Journal of Computing and Informatics ("Journal") the copyright in the manuscript identified above and any additional material (figures, tables, illustrations, software or other information intended for publication) submitted as part of or as a supplement to the manuscript ("Paper") in all forms and media throughout the world, in all languages, for the full term of copyright, effective when and if the article is accepted for publication. This transfer includes the right to reproduce and/or to distribute the Paper to other journals or digital libraries in electronic and online forms and systems.

I understand that I retain the rights to use the pre-prints, off-prints, accepted manuscript and published journal Paper for personal use, scholarly purposes and internal institutional use.

In certain cases, I can ask for retaining the publishing rights of the Paper. The Journal can permit or deny the request for publishing rights, to which I fully agree.

I declare that the submitted Paper is original, has been written by the stated authors and has not been published elsewhere nor is currently being considered for publication by any other journal and will not be submitted for such review while under review by this Journal.  The Paper contains no material that violates proprietary rights of any other person or entity. I have obtained written permission from copyright owners for any excerpts from copyrighted works that are included and have credited the sources in my article. I have informed the co-author(s) of the terms of this publishing agreement.


Copyright ©  Slovenian Society Informatika