Coresets for Farthest Point Problems in Hyperbolic Space
Eunku Park, Antoine Vigneron · 2025
Read Coresets for Farthest Point Problems in Hyperbolic Space by Eunku Park, Antoine Vigneron (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-27491.txt.
Introduction
Eunku Park and Antoine Vigneron build tiny coresets that answer farthest-point queries in hyperbolic space. A coreset is a small subset summarizing a huge point set. For fixed-dimensional hyperbolic space they construct constant-size coresets in linear time that guarantee both small relative and additive error for any query point.
Formally, the subset size and query time depend only on the error tolerance and dimension, not on the input size, after near-linear preprocessing. The coreset point nearly matches the true farthest distance in both senses. Consequences include efficient approximation algorithms for the diameter, the center, and the maximum spanning tree problems in hyperbolic space. Such summaries matter for network and hierarchy data naturally embedded in hyperbolic geometry, where farthest-point structure guides clustering and routing.
Catalog record
| CREATOR | Eunku Park, Antoine Vigneron |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-27491
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Coresets for Farthest Point Problems in Hyperbolic Space Thanks: E. Park was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. RS-2024-00414849). E. Park and A. Vigneron were supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. 2022R1F1A107586911). Eunku Park, Antoine Vigneron Abstract We show how to construct in linear time coresets of constant size for farthest point problems in fixed-dimensional hyperbolic space. Our coresets provide both an arbitrarily small relative error and additive error ε \varepsilon . More precisely, we are given a set P P of n n points in the hyperbolic space ℍ D \mathbb{H}^{D} , where D = O ( 1 ) D=O(1) , and an error tolerance ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) . Then we can construct in O ( n / ε D ) O(n/\varepsilon^{D}) time a subset P ε ⊂ P P_{\varepsilon}\subset P of size O ( 1 / ε D ) O(1/\varepsilon^{D}) such that for any query point q ∈ ℍ D q\in\mathbb{H}^{D} , there is a point p ε ∈ P ε p_{\varepsilon}\in P_{\varepsilon} that satisfies d H ( q , p ε ) ⩾ ( 1 − ε ) d H ( q , f P ( q ) ) d_{H}(q,p_{\varepsilon})\geqslant(1-\varepsilon)d_{H}(q,f_{P}(q)) and d H ( q , p ε ) ⩾ d H ( q , f P ( q ) ) − ε d_{H}(q,p_{\varepsilon})\geqslant d_{H}(q,f_{P}(q))-\varepsilon , where d H d_{H} denotes the hyperbolic metric and f P ( q ) f_{P}(q) is the point in P P that is farthest from q q according to this metric. This coreset allows us to answer approximate farthest-point queries in time O ( 1 / ε D ) O(1/\varepsilon^{D}) after O ( n / ε D ) O(n/\varepsilon^{D}) preprocessing time. It yields efficient approximation algorithms for the diameter, the center, and the maximum spanning tree problems in hyperbolic space. 1 Introduction Nearest-neighbor searching is a fundamental problem in computational geometry where, given a dataset P of n points, we want to quickly return a point of P that is closest to a query point q . If interpoint distances can be computed in O(1) time, a query can be answered by brute force in O(n) time, so the goal is to design data structures that answer queries in sublinear time after some preprocessing. For instance, in the Euclidean plane \mathbb{R}^{2} , nearest-neighbor queries can be answered in O(\log n) time after O(n\log n) preprocessing time by computing the Voronoi diagram of P [ 3 ] . Unfortunately, the worst case complexity of the the Voronoi diagram in the D -dimensional Euclidean space \mathbb{R}^{D} is \Theta(n^{\lceil D/2\rceil}) , so this approach is often impractical in dimension D\geqslant 3 . In order to address this issue, an approximate version of nearest-neighbor searching, called approximate nearest-neighbor searching (ANN) has been considered where, instead of returning the closest point to q , we return a point whose distance from q is at most (1+\varepsilon) times the optimal, for a given relative error tolerance \varepsilon\in(0,1) . Arya et al. showed that in fixed-dimensional Euclidean space (i.e. in \mathbb{R}^{D} where D=O(1) ), ANN queries can be answered in O(\log(n)/\varepsilon^{D}) time after O(n\log n) preprocessing time [ 2 ] . A related problem is farthest-neighbor searching: Preprocess P so that a point in P that is farthest from a query point q can be found efficiently. This problem can be solved exactly using the farthest-point Voronoi diagram , but unfortunately, in the worst case, it has the same size \Theta(n^{\lceil D/2\rceil}) as the Voronoi diagram in dimension D . Agarwal et al. [ 1 ] gave an efficient data structure for (1-\varepsilon) -approximate farthest neighbors in fixed dimension: After O(n/\varepsilon^{(D-1)/2}) preprocessing time, a point whose distance from q is at least (1-\varepsilon) times the maximum is returned in O(1/\varepsilon^{(D-1)/2}) time. The idea is to compute the set P_{\varepsilon} of extreme points of P along O(1/\varepsilon^{(D-1)/2}) directions distributed (roughly) uniformly on the unit sphere. This set P_{\varepsilon} has size O(1/\varepsilon^{(D-1)/2}) , and for any query point q , an approximate farthest point is in P_{\varepsilon} . Thus, it is a coreset for farthest point problems: It is a small subset of P , such that if we want to answer an approximate farthest-neighbor query on P , we can return a point in P_{\varepsilon} that is farthest from the query point. Coresets have been used for approximating the solutions of several computational geometry problems [ 11 ] . In this paper, we give a coreset of size O(1/\varepsilon^{D}) for farthest-point problems in fixed-dimensional hyperbolic space \mathbb{H}^{D} . This space is the unique D -dimensional Riemannian manifold with sectional curvature -1 at every point. It has several isometric models such as the hyperboloid model and the Poincaré half-space model [ 18 ] . For convenience, we will use the Poincaré ball model (\mathbb{B}^{D},d_{H}) where \mathbb{B}^{D} is the open unit ball of \mathbb{R}^{D} centered at the origin O , and d_{H} is the metric defined as follows. (See Section 2.1 for a more detailed introduction to the Poincaré ball model.) The hyperbolic length L_{H}(\Gamma) of a curve \Gamma in \mathbb{B}^{D} is given by the integral L_{H}(\Gamma)=\int_{\Gamma}ds where ds^{2}=4\frac{dx_{1}^{2}+\dots+dx_{D}^{2}}{\left(1-(x_{1}^{2}+\dots+x_{D}^{2})\right)^{2}}. (In the Euclidean case, ds is given by the relation ds^{2}=dx_{1}^{2}+\dots+dx_{D}^{2} .) For any two distinct points u,v\in\mathbb{B}^{D} , the curve [u,v] of minimum hyperbolic length between u and v is called a geodesic . The hyperbolic distance d_{H}(u,v) is the hyperbolic length of [u,v] . Figure 1: (a) A geodesic [u,v] in the Poincaré ball model \mathbb{B}^{D} . (b) Cone based approach: The input points are in blue. We add the red points to the coreset. The hyperbolic distance d_{H}(u,v) can be obtained by a closed formula. (Equations ( 1 )–( 3 ) in Section 2.1 .) It can be shown that the geodesics are arcs of circles that are orthogonal to the unit sphere \partial\mathbb{B}^{D} . (See Figure 1 a.) This metric space (\mathbb{B}^{D},d_{H}) has several properties that make it very different from the Euclidean space. For instance, the volume of a ball is exponential in its radius, instead of being polynomial, and thus some packing or discretization arguments used in the Euclidean case break down. On the other hand, triangles in hyperbolic space are thin : There is a constant \delta such that for any u,v,w\in\mathbb{B}^{D} , and for any point t\in[u,w] , there is a point in [u,v]\cup[v,w] that is at distance at most \delta from u . (For a more precise statement, see Section 5.1 .) One motivation for studying algorithms in hyperbolic spaces is that computer networks, and in particular the internet, are known to have better embeddings into hyperbolic space than into Euclidean spaces [ 19 ] . Recently, connections have also been found between machine learning and hyperbolic geometry, in particular in the context of hyperbolic neural networks [ 8 , 14 ] . Our results. We assume that we are in fixed dimension D=O(1) , and that \varepsilon\in(0,1) . We are given an input set P of n points in \mathbb{B}^{D} . For