An algorithm for approximate closest-point queries

Publisher Website
Google Scholar
Abstract
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 &egr;, and depends on a ratio &rgr;, 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&eegr;)O(1/&egr;)(d−1)/2 in time O(n2&eegr;)O(1/&egr;)(d−1). Here &eegr;=log(&rgr;/&egr;). With this data structure, a site is returned whose distance to a query point q is within 1+&egr; of the distance of the closest site. A query needs O(logn)O(1/&egr;)(d−1)/2 time, with high probability.

This publication has 0 references indexed in Scilit: