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