Nearest Point Query on 184M Points in E3 with a Uniform Grid.
Wm. Randolph Franklin · Canadian Conference on Computational Geometry · 2005
Nearpt3 is an algorithm and implementation to preprocess more than 10 fixed points in E and then perform nearest point queries against them. With fixed and query points drawn from the same distribution, Nearpt3’s expected preprocessing and query time are θ(1) per point, with a very small constant factor. The data structure is a uniform grid in E, typically with the same number of grid cells as points. The storage budget, in addition to the space to store the points themselves, is 4 bytes per grid cell plus 4 bytes per point. Nearpt3 has been tested on the UNC complete powerplant, on the largest ply datasets in the Georgia Tech Large Geometric Models Archive, and the Stanford Digital Michelangelo Project Archive. The examples with up to 30,000,000 points can be processed on a laptop computer, and the others, the largest of which is St Matthew with 184,088,599 points, on a Xeon.