Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.27491 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912679785922560 |
|---|---|
| author | Park, Eunku Vigneron, Antoine |
| author_facet | Park, Eunku Vigneron, Antoine |
| contents | 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$ of $n$ points in the hyperbolic space $\mathbb{H}^D$, where $D=O(1)$, and an error tolerance $\varepsilon\in (0,1)$. Then we can construct in $O(n/\varepsilon^D)$ time a subset $P_\varepsilon \subset P$ of size $O(1/\varepsilon^D)$ such that for any query point $q \in \mathbb{H}^D$, there is a point $p_\varepsilon \in P_\varepsilon$ that satisfies $d_H(q,p_\varepsilon) \geq (1-\varepsilon)d_H(q,f_P(q))$ and $d_H(q,p_\varepsilon) \geq d_H(q,f_P(q))-\varepsilon$, where $d_H$ denotes the hyperbolic metric and $f_P(q)$ is the point in $P$ that is farthest from $q$ according to this metric.
This coreset allows us to answer approximate farthest-point queries in time $O(1/\varepsilon^D)$ after $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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_27491 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Coresets for Farthest Point Problems in Hyperbolic Space Park, Eunku Vigneron, Antoine Computational Geometry 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$ of $n$ points in the hyperbolic space $\mathbb{H}^D$, where $D=O(1)$, and an error tolerance $\varepsilon\in (0,1)$. Then we can construct in $O(n/\varepsilon^D)$ time a subset $P_\varepsilon \subset P$ of size $O(1/\varepsilon^D)$ such that for any query point $q \in \mathbb{H}^D$, there is a point $p_\varepsilon \in P_\varepsilon$ that satisfies $d_H(q,p_\varepsilon) \geq (1-\varepsilon)d_H(q,f_P(q))$ and $d_H(q,p_\varepsilon) \geq d_H(q,f_P(q))-\varepsilon$, where $d_H$ denotes the hyperbolic metric and $f_P(q)$ is the point in $P$ that is farthest from $q$ according to this metric. This coreset allows us to answer approximate farthest-point queries in time $O(1/\varepsilon^D)$ after $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. |
| title | Coresets for Farthest Point Problems in Hyperbolic Space |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2510.27491 |