Coresets for Continuous $k$-Center in Hyperbolic Space

Abstract

We study the continuous $k$-center problem in fixed-dimensional hyperbolic space. The input is a finite point set $P\subset {\mathbb{H}}^D$, while the centers may be placed anywhere in the ambient space. A nonempty subset $P_{\epsilon }\subseteq P$ is an $\epsilon$-coreset if every exact optimal continuous $k$-center solution for $P_{\epsilon }$ is a $(1+\epsilon )$-approximate solution for $P$. Our construction uses Gonzalez's farthest-first traversal, whose radius $R_G$ gives a constant-factor estimate of the optimum. When $R_G$ is bounded, we map each cluster to the origin of the Poincaré ball model and apply a local Euclidean grid. For larger $R_G$, we partition each cluster into radial shells and project them onto representative hyperbolic spheres, avoiding a discretization of the ambient ball. By the hyperbolic law of cosines, the intersection of a hyperbolic ball with each sphere corresponds to a spherical cap. A recursive $k$-cap coverage certificate then replaces each shell with a radius-independent set of input witnesses that preserves its farthest-point behavior for every set of at most $k$ centers. The resulting coreset $P_{\epsilon }$ has size $|P_{\epsilon }|={\left(k/\epsilon \right)}^{O(kD)}$ and satisfies ${\Phi }_P(C_{P_{\epsilon }})\le (1+\epsilon ){\mathrm{OPT}}_k(P)$ for every optimal continuous $k$-center solution $C_{P_{\epsilon }}$ of $P_{\epsilon }$. It can be constructed in $O\left(nkD{\left(k/\epsilon \right)}^{O(kD)}\right)$ time. Consequently, for fixed $D$, $k$, and $\epsilon$, the coreset has constant size and can be computed in linear time. We complement this upper bound by showing that, for every fixed $D\ge 1$, every $k\ge 2$, and all sufficiently small $\epsilon$, there are instances for which every $\epsilon$-coreset has size $\Omega \left(k{\epsilon }^{-(D-1)/2}\right)$.

arXiv commentA counterexample to the methodology in the previous version was identified, and the argument has been replaced with a new spherical-cap certificate approach. A coreset-size lower bound has also been added