An algorithm for approximate closest-point queries

This paper gives an algorithm for approximately solving the post office problem: given n points (called sites) in d dimensions, build a data structure so that, given a query point q, a closest site to q can be found quickly. The algorithm is also given a relative error bound ε, and depends on a ratio ρ, which is no more than the ratio of the distance between the farthest pair of sites to the distance between the closest pair of sites. The algorithm builds a data structure of size O(nη)O(1/ε)(d−1)/2 in time O(n2η)O(1/ε)(d−1). Here η=log(ρ/ε). With this data structure, a site is returned whose distance to a query point q is within 1+ε of the distance of the closest site. A query needs O(logn)O(1/ε)(d−1)/2 time, with high probability.