B. Drost, S. Ilic A Hierarchical Voxel Hash for Fast 3D Nearest Neighbor Lookup German Conference on Pattern Recognition (GCPR), Saarbruecken, Germany, September 2013. (bib)
	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.
	This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each authors copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.