Better ϵ-Dependencies for Offline Approximate Nearest Neighbor Search, Euclidean Minimum Spanning Trees, and ϵ-Kernels
Sunil Arya, Timothy M. Chan · 2014
Recently, Arya, da Fonseca, and Mount [STOC 2011, SODA 2012] made notable progress in improving the ϵ-dependencies in the space/query-time tradeoffs for (1 + ϵ)-factor approximate nearest neighbor search in fixed-dimensional Euclidean spaces. However, ϵ-dependencies in the preprocessing time were not considered, and so their data structures cannot be used to derive faster algorithms for offline proximity problems. Known algorithms for many such problems, including approximate bichromatic closest pair (BCP) and approximate Euclidean minimum spanning trees (EMST), typically have factors near (1/ϵ)d/2±O(1) in the running time when the dimension d is a constant.