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 (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.