Abstract—In this paper, the general Nearest Neighbor (NN) search is mapped to the problem of finding NNs between clusters consisting of hexagonal cells. Namely, cells are clustered inside a Region of Interest (ROI) by using the hexagonal coordinate system. Two hexagonal ROI types with embedded hexagonal cells are selected and tessellated to form a tessellation ring. Three cell-based NN search algorithms are defined: Neighbor Cell-Based (NCB), Polygon Intersection-Based (PIB), and Euclidean Distance-Based (EDB). Algorithms are studied in conditions where accuracy is more important than computational cost, and their efficiency in predefined scenarios is examined. First, the NN clusters are extracted in the uniform hexagonal plane, after which the plane is distorted as ROIs in the tessellation ring are not unique. The study showed that acceptable results are obtained by using each algorithm, independently of whether the plane is distorted or not. However, NCB and EDB give approximate NN results, while PIB is the most efficient, outperforming both NCB and EDB in all measurement cases. It always provides the exact number of NNs, even in the critical border region between neighboring ROIs. Hence, it is concluded that the PIB algorithm is the most convenient to use in the general NN search between arbitrary-shaped hexagonal clusters.
 
Keywords—clusters, hexagon, Nearest Neighbors (NN)


Copyright © 2024 by the authors. This is an open access article distributed under the Creative Commons Attribution License (CC BY-NC-ND 4.0), which permits use, distribution and reproduction in any medium, provided that the article is properly cited, the use is non-commercial and no modifications or adaptations are made.