A Hierarchical Voxel Hash for Fast 3D Nearest Neighbor Lookup

We propose a data structure for nding the exact nearest neighbors in 3D in approximately O(log(log(N)) time. In contrast to standard approaches such as k-d-trees, the query time is independent of the location of the query point and the distribution of the data set. The method uses a hierarchical voxel approximation of the data point's Voronoi cells. This avoids backtracking during the query phase, which is a typical action for tree-based methods such as k-d-trees. In addition, voxels are stored in a hash table and a bisection on the voxel level is used to nd the leaf voxel containing the query point. This is asymptotically faster than letting the query point fall down the tree. The experiments show the method's high performance compared to state-of-the-art approaches even for large point sets, independent of data and query set distributions, and illustrates its advantage in real-world applications.     «

We propose a data structure for nding the exact nearest neighbors in 3D in approximately O(log(log(N)) time. In contrast to standard approaches such as k-d-trees, the query time is independent of the location of the query point and the distribution of the data set. The method uses a hierarchical voxel approximation of the data point's Voronoi cells. This avoids backtracking during the query phase, which is a typical action for tree-based methods such as k-d-trees. In addition, voxels are...     »