A Randomized Algorithm for Closest-Point Queries

An algorithm for closest-point queries is given. The problem is this: given a set S of n points in d-dimensional space, build a data structure so that given an arbitrary query point p, a closest point in S to p can be found quickly. The measure of distance is the Euclidean norm. This is sometimes called the post-office problem. The new data structure will be termed an RPO tree, from Randomized Post Office. The expected time required to build an RPO tree is O(n^ d / 2 (1 + ε ) ), for any fixed ε > 0, and a query can be answered in O(log n) worst-case time. An RPO tree requires O(n^ d / 2 (1 + ε ) ) space in the worst case. The constant factors in these bounds depend on d and ε. The bounds are average-case due to the randomization employed by the algorithm, and hold for any set of input points. This result approaches the Ω (n^ d / 2 ) worst-case time required for any algorithm that constructs the Voronoi diagram of the input points, and is a considerable improvement over previous bounds for $d > 3$. The main step of the construction algorithm is the determination of the Voronoi diagram of a random sample of the sites, and the triangulation of that diagram.