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

Eunku Park, Antoine Vigneron

We give an embedding of the Poincaré halfspace $H^D$ into a discrete metric space based on a binary tiling of $H^D$, with additive distortion $O(\log D)$. It yields the following r…