A Hybrid Point Indexing Structure Based on Orthogonal and Hexagonal Grids
Vojtěch Uher, Petr Gajdoš, Václav Snåšel · 2019
Multidimensional point indexing is an important task in many scientific areas such as computer graphics, image processing, geographic information systems, machine learning and pattern recognition. This paper proposes a novel 2D structure for efficient Fixed-Radius Nearest Neighbors queries. The standard methods are based on the recursive passage of a spatial tree or direct addressing of uniform grid cells with constant size. Each method is good for different type of data. Our algorithm uses space-filling curves to combine the principles of linear uniform grids and hierarchical recursion. Most of the preferred methods are based on the orthogonal grids. We introduce a novel hexagonal hierarchical structure and provide a comparison of both approaches.