Nearest neighbor queries in metric spaces

Given a set Sofn sites (points), andadistance measure cl, the nearest neighbor searching problem, or post office problem, istobuild adatastructure sothatgiven a query point q, the site nearest to g can be found quickly. This paper gives data structures for this problem when the sites and queries are in a metric space. The data structures can be analyzed when the metric space satisfies a certain spherepacking bound. Onedata structure, denoted D(S), requires expected O(n)(lgn)O(lK 1gT(s)) time to build. Here 'Y(S) is the distance ratio of S, the ratio of the distance between the farthest pair of points in S to the distance between the closest pair. The constant factors in the bound depend on the sphere-packing bound. When the query pointqis arandom element of {q} uS, as for example when q and the points of S are randomly generated from a common distribution, then the query time is expected (lgn)O(lglgrfs)).