Source-linked AI summary
Optimal Coresets for Hyperbolic Farthest-Point Queries via Ideal-Boundary Envelopes
Eunku Park
TL;DR
The paper asks how small a coreset can be while approximating hyperbolic farthest-point queries under additive and multiplicative guarantees. It reduces query loss to ideal-boundary envelope approximation and proves a matching optimal size bound, with a lower bound that holds for either guarantee separately.
Problem
The optimal dependence on ε for hyperbolic farthest-point coresets was unknown, despite a prior O(ε^-D) bound; the fixed hyperbolic metric also gives additive error an intrinsic scale.
Source: §1 · p. 1Method
The paper exactly represents worst-case query loss as logarithmic loss between ideal-boundary envelopes, then combines minimum-enclosing-ball normalization with a Euclidean kernel for the upper bound.
Source: §1 · pp. 3–4Results
For fixed D ≥ 2, the optimal worst-case coreset size is Θ(ε^-(D-1)/2), and the lower bound applies even when either guarantee is required separately.
Source: §1 · p. 2, §7 · p. 17Takeaways & Limitations
The ideal-boundary representation and Euclidean convex-hull approximation yield matching bounds, with a spherical packing and antipodal queries establishing the lower bound.
Source: §7 · p. 18Streaming and dynamic maintenance remain open because insertions or deletions can change the minimum-enclosing-ball normalization.
Source: §7 · p. 18
Abstract
from arXiv · showhide
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 $\Theta\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.
1 Introduction
The paper determines the optimal worst-case size of hyperbolic farthest-point coresets by reducing uniform query loss to approximation on the ideal boundary. It proves matching upper and lower bounds for fixed dimension.
Relation to previous work
- The result sharpens Park and Vigneron’s O(ε^-D) bound; the ideal-boundary reduction and normalization allow a kernel in R^D rather than R^(D+1).The resulting exponent matches the Euclidean ε-kernel exponent, while the hyperbolic additive guarantee uses the fixed hyperbolic metric.Source: §1 · pp. 2–3
Main result
- For every fixed D ≥ 2, the worst-case minimum size of a coreset satisfying both requirements is Θ(ε^−(D−1)/2), and this ε-dependence is optimal.Source: §1 · pp. 2–3
Our approach
- The ideal-boundary envelope identity equates worst-case finite-query loss with the maximum logarithmic gap between input and coreset envelopes.It reduces approximation over all hyperbolic queries to approximation over the (D−1)-dimensional family of ideal directions.Source: §1 · pp. 3–4
- Minimum-enclosing-ball normalization makes boundary scores convex, Lipschitz functions of D-dimensional spatial coordinates, so a Euclidean kernel approximates them simultaneously.The structure theorem transfers this approximation into additive and multiplicative guarantees.Source: §1 · p. 3
- A spherical packing at angular scale √ε, with radius-one points and antipodal queries, makes every selected input point indispensable.The hyperbolic cosine law establishes the lower bound for both guarantees.Source: §1 · pp. 2–3
2 Preliminaries
The preliminaries establish the hyperboloid model and ideal-boundary directions used in the reduction, then review Euclidean kernels and their convex-hull approximation guarantees.
2.1 The hyperboloid model
- The hyperboloid model uses a Lorentz form for hyperbolic distance, and isometries can move a chosen point to the origin without changing distances.The ideal boundary is identified with the unit sphere of ray directions; the minimum-enclosing-ball center is unique.Source: §2.1 · pp. 4–5
2.2 Euclidean δ-kernels
- The paper reserves δ for Euclidean kernel accuracy and uses ε for hyperbolic coreset accuracy; the kernel’s construction-time exponent slack does not affect its size.The stated construction is deterministic in the real-RAM model for fixed D ≥ 3 and fixed α > 0.Source: §2.2 · pp. 5–6
- A Euclidean δ-kernel preserves every directional width to within relative error δ, and its convex hull approximates the input convex hull in Hausdorff distance.The kernel theorem supplies size and construction-time bounds used by the upper-bound argument.Source: §2.2 · p. 5
3 The Structure Theorem
The section represents farthest-point losses through positive score functions on the ideal boundary. Its exact loss identity equates the supremum over finite queries with the maximum logarithmic gap between envelopes.
3.1 Boundary scores and ideal-boundary envelopes
- Each input point induces a positive boundary score, and the pointwise maximum of these scores is the set's ideal-boundary envelope.The logarithm of a point's score gives its additive distance offset as a query moves far along the corresponding ray.Source: §3 · p. 6, §3.1 · p. 6
3.2 Distance estimates along geodesic rays
- Distance estimates along geodesic rays express each point's distance as the ray parameter plus a logarithmic score term, within explicit bounds.The ray from an arbitrary starting point to a fixed ideal endpoint is asymptotic to the standard ray in that direction.Source: §3.2 · p. 7
3.3 The exact loss identity
- The supremum additive loss over finite queries equals the maximum logarithmic gap between the corresponding ideal-boundary envelopes.The finite-query supremum need not be attained, but a ray toward a maximizing ideal direction approaches it.Source: §3.3 · p. 8
- Moving beyond a farthest input point preserves that point as farthest, so loss does not decrease along the resulting ray.This connects finite queries to boundary-direction limits in proving the exact identity.Source: §3.3 · p. 8
4 The Upper Bound
The upper-bound construction normalizes the input around its minimum enclosing ball, then uses a Euclidean kernel to approximate boundary-envelope scores. The resulting selected input points provide the coreset guarantees.
4.1 Balancing at the minimum enclosing ball
- The minimum-enclosing-ball active directions balance around the origin, a condition used to control the normalized representation.If all active directions lay strictly on one side, shifting the center toward that side would contradict minimality.Source: §4.1 · p. 9
4.2 A normalized Euclidean representation
- After centering and scaling, the Euclidean point set has controlled diameter and its ideal-boundary envelope stays bounded away from zero.These bounds let the Euclidean approximation control absolute and logarithmic error.Source: §4.2 · p. 10
4.3 The coreset construction
- A Euclidean kernel preserves directional maxima across the normalized set, and the selected transformed points map one-to-one to original inputs.The construction uses the same normalization when evaluating selected points.Source: §4.3 · pp. 11–12
- The upper-bound theorem returns a coreset from the input, and the same selected set is stated to satisfy both guarantees.For small enclosing radius, the construction's loss scales with that radius; for larger radius, the loss is bounded by ε.Source: §4.3 · pp. 11–12
5 The Lower Bound
The lower bound uses separated directions on a fixed-radius hyperbolic sphere and queries in their opposite directions. The resulting angular distance gaps make each constructed input point necessary.
5 The Lower Bound
- A spherical packing and antipodal queries yield Ω(ε^−(D−1)/2) points, each necessary for either coreset guarantee.The construction uses points on the radius-one sphere and makes the designated point farther than all others at its associated query.Source: §5 · p. 12, §5.3 · p. 14
5.1 A spherical packing
- A θ-separated spherical packing supplies the many directions used to construct the hard instance.The stated packing result applies for fixed D ≥ 2 and 0 < θ ≤ 1.Source: §5.1 · p. 12, §5 · p. 12
5.2 A quadratic angular gap
- An angular separation of 6√ε creates a distance loss of at least 9ε/4, exceeding both stated tolerances at a query with farthest distance two.The quadratic angular gap follows from the hyperbolic cosine law for points at radius one.Source: §5.2 · p. 13
5.3 The hard instance
- Omitting the designated point violates both additive and multiplicative requirements at its associated antipodal query.The lower bound also applies to queries restricted to the radius-one sphere.Source: §5.3 · p. 14
6 Algorithmic Construction
The algorithm computes a hyperbolic minimum enclosing ball, normalizes spatial coordinates, and selects a Euclidean kernel. Its running-time analysis treats the enclosing-ball computation as an LP-type problem and specifies the computational assumptions for its primitives.
6 Algorithmic Construction
- The algorithm computes the minimum enclosing ball, forms normalized spatial points, selects a Euclidean δ-kernel, and returns the corresponding original inputs.The normalization and kernel selection are the same as in the upper-bound proof.Source: §6 · p. 15
6.1 The minimum enclosing ball as an LP-type problem
- The hyperbolic minimum-enclosing-ball problem has LP-type combinatorial dimension at most D + 1 and admits randomized expected O(n) solution time for fixed D under the stated primitive assumptions.The bound assumes constant-time violation tests and basis computations on bounded-size constraint sets.Source: §6.1 · p. 16
6.2 Algebraic primitives
- For fixed D, a minimum enclosing ball of at most D + 2 hyperboloid points can be computed in constant time using arithmetic, comparisons, and square roots.The construction enumerates candidate subsets and retains feasible enclosing balls.Source: §6.2 · pp. 16–17
6.3 Running time
- The stated construction-time bound is expected, while the Euclidean kernel construction and subsequent steps are deterministic.The expectation comes from randomized LP-type computation; the result assumes fixed D and α.Source: §6.3 · p. 17
7 Conclusion
The conclusion establishes the optimal worst-case coreset size for every fixed dimension D ≥2, with the lower bound holding even when either guarantee is required separately. It summarizes the matching boundary-envelope upper-bound and spherical-packing lower-bound strategies.
7 Conclusion
- The optimal worst-case coreset size is established for every fixed D ≥2, and the lower bound holds even when either approximation guarantee is required separately.Source: §7 · p. 17
- The upper bound uses the exact ideal-boundary envelope identity and Euclidean convex-hull approximation, while spherical packing with antipodal queries gives the lower bound.Source: §7 · p. 18
- For fixed D ≥3 and α > 0, the construction has a real-RAM expected-time bound; randomness comes from minimum-enclosing-ball computation, while exponent slack comes from the deterministic kernel algorithm.Source: §7 · p. 18
- Under the standard invariant Riemannian metric, Siegel spaces of matrix size at least two admit no coreset bound depending only on dimension and ε for absolute additive error; relative or radius-dependent guarantees are suggested.The Hilbert metric on the Siegel–Klein disk requires separate analysis.Source: §7 · p. 18
- Streaming and dynamic maintenance remain open because insertions or deletions may change the minimum-enclosing-ball normalization; summaries with representatives outside the input are another open direction.Source: §7 · p. 18