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(ε(1-d)/2 n log n) preprocessing time and O(ε(1-d)/2 log n) query time achieves approximation factor 1+ε for any given 0<ε<1; a variant reduces the ε-dependence by a factor of ε-1/2. For any arbitrary d, a data structure with O(d2n log n) preprocessing time and O(d2 log n) query time achieves approximation factor O(d3/2).
Original language | English (US) |
---|---|
Pages | 352-358 |
Number of pages | 7 |
DOIs | |
State | Published - 1997 |
Externally published | Yes |
Event | Proceedings of the 1997 13th Annual Symposium on Computational Geometry - Nice, Fr Duration: Jun 4 1997 → Jun 6 1997 |
Other
Other | Proceedings of the 1997 13th Annual Symposium on Computational Geometry |
---|---|
City | Nice, Fr |
Period | 6/4/97 → 6/6/97 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics