CS Paper Radar

Optimal Coresets for Hyperbolic Farthest-Point Queries via Ideal-Boundary Envelopes

Eunku Park

cs.CG ·submitted 2026-10-01 06:12 UTC · v1
theory

Abstract

We study coresets for farthest-point queries in hyperbolic space. Given a nonempty finite set $P \subset \mathbb{H}^D$ and $0<\varepsilon \le 1$, we seek a coreset $P_{\varepsilon} \subseteq P$ whose farthest distance from every query point underestimates that of $P$ by at most an additive $\varepsilon$ and retains at least a $1-\varepsilon$ fraction of it. For every fixed $D \ge 2$, we prove that the optimal worst-case coreset size is $Θ\bigl(\varepsilon^{-(D-1)/2}\bigr)$. Our main geometric ingredient is an exact reduction from hyperbolic queries to an upper envelope on the ideal boundary. In the hyperboloid model, each input point induces a positive boundary-score function whose logarithm gives its asymptotic distance offset along geodesic rays. We define the \emph{ideal-boundary envelope} as the pointwise maximum of these functions and prove that the supremum additive loss over all queries equals the maximum logarithmic gap between the input and coreset envelopes. For the upper bound, we move the minimum-enclosing-ball center to the origin and normalize the spatial coordinates, obtaining a bounded Euclidean point set whose boundary envelope is bounded away from zero. A standard Euclidean kernel then approximates all directional score maxima simultaneously, and the structure theorem yields both guarantees. For the lower bound, a spherical packing on a fixed-radius hyperbolic sphere, together with antipodal queries and the hyperbolic cosine law, makes every input point indispensable, matching the upper bound even for either guarantee separately.

Closest papers

Nearest neighbours by meaning across the whole index.

Hyperbolic Sphericity

cs.CG ·2026-10-01 ·Thomas Bläsius, Lennart Großkreutz, Jean-Pierre von der Heydt
similarity 0.66
Abstract

The sphericity of a graph is the minimum dimension d such that the graph has an intersection representation of d-dimensional balls of equal radius. While sphericity has been studied in Euclidean space, we initiate the study of hyperbolic sphericity. The hyperbolic sphericity of a graph can be significantly smaller than its Euclidean counterpart, but, contrary to the Euclidean setting, depends strongly on the radius of the balls. We show that, if the radius of the balls can be chosen depending on the graph, the hyperbolic sphericity is upper bounded by the Euclidean sphericity. This extends a previous result for 2-dimensional hyperbolic space, i.e., uniform disk graphs, to arbitrary dimensions. Moreover, our proof is significantly simpler. If we fix the radius, i.e., do not make it dependent on the graph, we show that hyperbolic sphericity can be larger than Euclidean sphericity, but by at most 1. Additionally, we study how hyperbolic sphericity changes with the ball radius. We show that choosing a larger radius can substantially decrease the sphericity while increasing it by at most 1. We also provide a construction of a graph where the sphericity oscillates between different values as the radius increases. Besides being theoretically interesting, we note that these results are relevant for graph embeddings in machine learning, where one is interested in low-dimensional numeric representations of symbolic data like graphs.

0.28

The Hyperbolic Surface Distance, Diameter, and Dirichlet Problems

cs.CG ·2026-09-09 ·Vincent Despre, Auguste Gezalyan, Marc Pouget
similarity 0.66
Abstract

Despite the prominence of hyperbolic surfaces in mathematics, basic algorithmic questions about them, even computing the distance between two points, have remained open, leaving many features of these surfaces inaccessible. The classical machinery assumes a polyhedral structure absent on a smooth surface. We remove these obstacles. We begin with an efficient $O(g^2)$ algorithm for the distance between two points, where $g$ is the genus of the surface. Building on it, we obtain an $O(g^2 \log g)$ method for answering distance queries from a fixed source and, as a consequence, for recentering a Dirichlet domain around an arbitrary point. This understanding of distances on the surface then lets us approximate the diameter to within any $\eps$ in time $O(g^3 \log g / \eps^2)$. We further show that the diameter, a single real number encoding a great deal about the surface, is exactly computable. Its hyperbolic cosine is an algebraic number over the field encoding the coefficients of the hyperbolic isometries defining the surface.

0.14

On the weighted hard-core model and Rado's covering problem for congruent Euclidean balls

cs.DM math.MGmath.CAmath.CO+1 ·2026-08-10 ·Chengfei Xie, Gennian Ge
theory similarity 0.63
Abstract · 17 pages; any comments are welcome

Let $K$ be a symmetric convex body in $\mathbb{R}^d$ and let $f(K)$ denote the largest constant $c$ such that every finite collection of translates of $K$ contains a pairwise disjoint subcollection whose total volume is at least $c$ times the volume of the union of the original collection. The classical Vitali covering lemma gives $f(K)\geq3^{-d}$. In this paper, we establish two improvements. First, by a purely combinatorial argument, we prove that $$ f(K)\geq \frac{2}{3^d + 2^d} $$ for every symmetric convex body $K$. This improves the Vitali bound by a factor tending to $2$ as $d$ tends to infinity. Second, using a weighted hard-core model together with a weighted geometric estimate for intersections of Euclidean balls, we show that, for all sufficiently large $d$, $$ f(B^d)\geq \left( \log\frac{3}{1+\sqrt3} -O\left(\frac{\log d}{d}\right) \right)d\,3^{-d}, $$ where $B^d$ is the unit Euclidean ball in $\mathbb{R}^d$. Thus, the classical lower bound is improved by a factor of order $d$.

0.38

Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructions

cs.DS cs.CL ·2026-09-06 ·Ofek I. Cohen
theory similarity 0.63
Abstract

A query-oblivious coreset for a softmax-attention head is a subset of the key--value pairs whose attention output is within $\varepsilon$ of the full one for every query in a ball. With $ρ$ the query radius times the centred key radius, we build such coresets of size $O(e^ρ(\sqrt{d_v}+\sqrt{d_k\log(1+ρ)})/\varepsilon)$ in randomised polynomial time, improving the existential $O(\sqrt d\,e^{ρ+\frac12\logρ+o(\log\logρ)}/\varepsilon)$ of Liberty, Andoni and Kleiner to within $\sqrt{\log(1+ρ)}$ of their $Ω(\sqrt d\,e^ρ/\varepsilon)$ lower bound: a spherical lift of both balls into one exponential-kernel instance admits the Bozzai--Rothvoss chaining bound, and Chevet's inequality splits key from value dimension. A sampling cap $O(e^{2ρ}/\varepsilon^{2})$ completes the envelope, and in fixed dimension Tai's diameter-free bound removes the logarithm. A census of every head of Qwen2.5-7B-Instruct and Llama-3.1-8B-Instruct finds $ρ\ge24.100$, so every whole-ball bound with a factor $e^ρ/\varepsilon$ prescribes a coreset larger than the cache: the algorithmic contribution is asymptotic on these models.

0.23

A quantitative tree-likeness bound from average hyperbolicity

cs.DS math.PRmath.COmath.MG ·2026-09-16 ·Joon-Hyeok Yim
theory similarity 0.63
Abstract · 13 pages, 3 figures. Added comments on ultrametric fitting corollary, and AI statements

Chatterjee and Sloman proved that a bounded measurable similarity function with sufficiently small average Gromov hyperbolicity admits a tree representation with small mean approximation error. Their argument uses a weighted version of Szemerédi's regularity lemma and does not yield explicit quantitative bounds. Here, we establish a tighter relation between average hyperbolicity and mean tree approximation error. For a similarity function $s:S\times S\to[0,b]$, we prove that $$\operatorname{Tree}(s) \leq (63/e)^{1/3} \sqrt[3]{b^2 \operatorname{Hyp}(s)} \leq 2.8512 \sqrt[3]{b^2 \operatorname{Hyp}(s)}.$$ The proof uses a simple pivoting construction inspired by \KwikCluster. We also discuss the optimal dependence on average hyperbolicity, including a square-root lower bound, and connections with ultrametric fitting.

0.28

New Quantitative Bounds for the $(p,q)$-Theorem for Unions of Convex Sets

cs.CG math.CO ·2026-08-13 ·Chaya Keller, Shakhar Smorodinsky
theory similarity 0.61
Abstract · 21 pages

A set in $\mathbb{R}^d$ is $s$-convex if it is the union of at most $s$ convex sets. A family $F$ satisfies the $(p,q)$ property if among any $p$ sets in $F$, some $q$ intersect. Let $\mathrm{HD}_d^{(s)}(p,q)$ be the minimum number of points needed to pierce a finite family of $s$-convex sets that satisfies the $(p,q)$-property. Alon and Kalai (1995) proved that $\mathrm{HD}_d^{(s)}(p,q)$ exists for any $p \geq q \geq d+1$ and any $s \geq 1$, but the quantitative bounds they obtained are very loose. We present several improved upper and lower bounds, for a general $d$ and for $s$-intervals of the line (i.e., $\mathrm{HD}_1^{(s)}(p,q)$). In particular, we prove the following: (i) For every $d\ge2$, $s \geq 1$ and $δ>0$, if $p>q$ and $q\ge C_d\log(e sp)$, then $\mathrm{HD}_d^{(s)}(p,q) \le p-q+1 + O_{d,δ}((s \cdot \tfrac{p}{q} \cdot \log \tfrac{esp}{q})^{ρ_d+δ}),$ where $ρ_d<d$ is the exponent in the weak epsilon-net theorem of Rubin (2022). (ii) For $s \geq 1$, $p \geq q \geq 2$ and $q\ge C_0s\log(2s)\log(ep)$, $p-q+s \leq \mathrm{HD}_1^{(s)}(p,q) \leq p-q+2s+1$. This result provides the first near-tight estimate for $\mathrm{HD}_1^{(s)}(p,q)$ for $q>2$. (iii) For any fixed $s$, there are an integer $κ_s\in\{s,\ldots,2s\}$ and constants $C_s,p_s>0$ such that, whenever $p\ge p_s$ and $q\ge C_s\log(ep)$, $ \mathrm{HD}_1^{(s)}(p,q)\in\{p-q+κ_s,\;p-q+κ_s+1\}. $ Interestingly, this two-value concentration result holds, although the exact value of the threshold remains unknown. (iv) For any $s \geq 1$, $\mathrm{HD}_3^{(s)}(p,4) \geq sp^{2-o(1)}$. Already for families of convex sets, this significantly improves the best known lower bound on $\mathrm{HD}_d^{(1)}(p,d+1)$, for all $d \geq 3$.

0.38

Tight Coreset Bounds for $(k,z)$-Clustering in Euclidean and Doubling Metrics

cs.DS cs.CG ·2026-10-25 ·Junqiu Hu, Lingxiao Huang, Jian Li, Baoduo Xu
theory similarity 0.61
Abstract

We determine the optimal worst-case size of strong coresets for $(k,z)$-clustering in Euclidean spaces and doubling metrics, up to polylogarithmic factors. In Euclidean space, previous lower bounds matched the best upper bounds only for $\varepsilon\gtrsim k^{-1/(z+2)}$. We close the gap for arbitrarily small $\varepsilon$, establishing the optimal size $\widetildeΘ(\min\{k^{(2z+2)/(z+2)}\varepsilon^{-2},\,k\varepsilon^{-z-2}\})$ for every fixed $z\ge1$, all $k\ge1$, and $0<\varepsilon<1$. Our lower bound replaces each offset in a previous hard instance by a group of distinct offsets. A fixed family of $k$-center queries and four-wise independent signs force a large relative cost error for every sufficiently small subset with arbitrary nonnegative weights. For doubling metrics of dimension $D$, we resolve the previously unmatched bounds for $z>2$. We prove an upper bound of $\widetilde O(k^{2-2/z}D\varepsilon^{-2})$ and a lower bound that, together with known upper bounds, establishes the optimal size $\widetildeΘ(kD\min\{k^{1-2/z}\varepsilon^{-2},\,\varepsilon^{-z}\})$ for fixed $z>2$, $0<\varepsilon\le\varepsilon_z$, and $D\ge C_z\log(2/\varepsilon)$, where $C_z>0$ and $\varepsilon_z\in(0,1)$ depend only on $z$. The lower bound exploits the ability to encode $Θ(D)$ independent signs per center without diluting relative cost discrepancy. For the upper bound, we use independent, unbiased two-point summaries that exactly preserve cluster mass and anchor cost, combined with iterative size reduction.

0.21

Navigable Graphs for Low-Dimensional Hyperbolic Spaces

cs.DS cs.CG ·2026-10-17 ·Chengyuan Deng, Jie Gao, Kuijun Liu, Kevin Lu, Feng Luo +2 more
theory similarity 0.61
Abstract

A directed graph on a point set $P$ in a metric space $(X,d)$ is navigable if for every ordered pair of distinct points $s,t \in P$, $s$ has an out-neighbor $v$ with $d(v,t) < d(s,t)$, so greedy routing always reaches the destination. Existing work on sparse navigable graphs mostly assumes bounded doubling dimensions. In this paper, we show that constant-dimensional hyperbolic spaces that do not have bounded doubling dimension also admit sparse navigable graphs. Specifically, for an $n$-point set in $\mathbb H^k$ with a constant $k$, we construct a navigable graph of size $O_k(n)$ with Steiner points, where each node has constant out-degree. We also show that Steiner points can be removed: every $n$-point set in $\mathbb H^k$ admits a navigable graph on the input points alone with $O_k(n)$ edges, though a single vertex may have out-degree $Ω(n)$. Furthermore, with a refined construction with $O_k(n\log n)$ edges and an accompanying greedy routing algorithm, we can obtain routing paths of expected $O(\log ^2 n)$ in both settings with or without Steiner points. With Steiner points, the maximum out-degree is bounded by $O_k(\log n)$. We complement these upper bounds with matching lower bound results. In the hyperbolic plane, there are point sets for which every navigable graph requires maximum out-degree $Ω(n)$, so the maximum linear out-degree above is unavoidable and constant out-degree is only possible with Steiner points. Next, we show that for every constant $α>1$, an $α$-navigable graph may require $Ω(n^2)$ edges, which rules out the standard route of using $α$-navigability to obtain greedy paths of bounded hops. Last, once the dimension $k$ reaches $Ω(\log n)$, there are point sets for which every navigable graph may require $n^{3/2-o(1)}$ edges, matching the upper bounds for general metrics.

0.18