Embeddings and near-neighbor searching with constant additive error for hyperbolic spaces

We give an embedding of the Poincar\'e halfspace HD into a discrete metric space based on a binary tiling of HD, with additive distortion O (D). It yields the following results. We show that any subset P of n points in HD can be embedded into a graph-metric with 2^O (D) n vertices and edges, and with additive distortion O (D). We also show how to construct, for any k, an O (k D) -purely additive spanner of P with 2^O (D) n Steiner vertices and 2^O (D) n ₖ (n) edges, where ₖ (n) is the kth-row inverse Ackermann function. Finally, we present a data structure for approximate near-neighbor searching in HD, with construction time 2^O (D) n n, query time 2^O (D) n and additive error O (D). These constructions can be done in 2^O (D) n n time.