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

2024/02/22 by Eunku Park, Park, Eunku, Antoine Vigneron +1 · 2 citations
Mathematics · #Computational Geometry (cs.CG) #FOS: Computer and information sciences #Mathematical Dynamics and Fractals

paper · pdf · doi:10.48550/arxiv.2402.14604

openalex publication_date 2024/02/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 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(klog D)-purely additive spanner of P with 2^O(D)n Steiner vertices and 2^O(D)n ⋅ λ_k(n) edges, where λ_k(n) is the kth-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.

Cited by

• Coresets for Farthest Point Problems in Hyperbolic Space
• Near-Optimal Dynamic Steiner Spanners for Constant-Curvature Spaces

Related

• A Quadtree, a Steiner Spanner, and Approximate Nearest Neighbours in Hyperbolic Space
• Near-Optimal Dynamic Steiner Spanners for Constant-Curvature Spaces
• Near Neighbor Search via Efficient Average Distortion Embeddings
• Additive approximation algorithm for geodesic centers in δ-hyperbolic graphs
• Hyperbolic Distance Matrices