Electronic Resource
Springer
Discrete & computational geometry
20 (1998), S. 359-373
ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. This paper proposes new methods to answer approximate nearest neighbor queries on a set of n points in d -dimensional Euclidean space. For any fixed constant d , a data structure with O( $\varepsilon$ (1-d)/2 n log n) preprocessing time and O( $\varepsilon$ (1-d)/2 log n) query time achieves an approximation factor 1+ $\varepsilon$ for any given 0 〈 $\varepsilon$ 〈 1; a variant reduces the $\varepsilon$ -dependence by a factor of $\varepsilon$ -1/2 . For any arbitrary d , a data structure with O(d 2 n log n) preprocessing time and O(d 2 log n) query time achieves an approximation factor O(d 3/2 ) . Applications to various proximity problems are discussed.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009390
Permalink
|
Location |
Call Number |
Expected |
Availability |