Nearest-Neighbor Queries with Well-Spaced Points

We assume we are given a set of points that have the property that their Voronoi diagram-restricted to some suitable bounding box-consists of only fat cells. We call such points well-spaced points. We give a linear-sized data structure for finding the nearest neighbor to a query point among well-spaced points in O(log n) time. We further show how to extend the results to higher dimensions. Finally, we show how to find the Voronoi diagram of these points in O(n log n) time in 3 dimensions.