We present a new approach to $\varepsilon$-approximate nearest-neighbor queries in fixed dimension under a variety of non-Euclidean …