Embeddings and near-neighbor searching with constant additive error for hyperbolic spaces
<|reference_start|>Embeddings and near-neighbor searching with constant additive error for hyperbolic spaces: We give an embedding of the Poincar\'e 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 results. We show that any subset $P$ of $n$ points in $H^D$ can be embedded into a graph-metric with $2^{O(D)}n$ vertices and edges, and with additive distortion $O(\log D)$. We also show how to construct, for any $k$, an $O(k\log D)$-purely additive spanner of $P$ with $2^{O(D)}n$ Steiner vertices and $2^{O(D)}n \cdot \lambda_k(n)$ edges, where $\lambda_k(n)$ is the $k$th-row inverse Ackermann function. Finally, we show how to construct an approximate Voronoi diagram for $P$ of size $2^{O(D)}n$. It allows us to answer approximate near-neighbor queries in $2^{O(D)}+O(\log n)$ time, with additive error $O(\log D)$. These constructions can be done in $2^{O(D)}n \log n$ time.<|reference_end|>
@article{park2024embeddings,
    title={Embeddings and near-neighbor searching with constant additive error for
  hyperbolic spaces},
    author={Eunku Park and Antoine Vigneron},
    journal={arXiv preprint arXiv:2402.14604},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.14604},
    primaryClass={cs.CG}
}