arXiv:2606.16061 · v3
Coresets for Continuous $k$-Center in Hyperbolic Space
摘要
We study coresets for the continuous $k$-center problem in fixed-dimensional hyperbolic space $\mathbb H^D$, where centers may lie anywhere in the space. For an input set $P$ of $n$ points, we construct an unweighted coreset of size $(k/\varepsilon)^{O(kD)}$ in $O(nkD(k/\varepsilon)^{O(kD)})$ time, independent of the enclosing radius. Every exact optimal solution for the coreset is a $(1+\varepsilon)$-approximation for $P$. The same construction also yields a strong coreset after adjusting the accuracy parameter. Our method combines local Euclidean grids at bounded scales with radial shells at larger scales. Hyperbolic balls induce spherical caps on representative spheres, whose multiplicative enlargement can be controlled by additive hyperbolic distance errors. A recursive ball-coverage certificate then selects a radius-independent set of input witnesses. We establish lower bounds of $Ω_D(k\varepsilon^{-D})$ for $k\ge 8D$ and sufficiently small $\varepsilon$, and $2^{Ω(k)}$ for $D\ge2$ when $\varepsilon=Θ(1/k)$, ruling out bounds polynomial jointly in $k$ and $1/\varepsilon$. For $k$ sufficiently separated clusters, we obtain simultaneous additive and multiplicative weak coreset guarantees, with optimal worst-case size $Θ_D(k\varepsilon^{-(D-1)/2})$ when both errors equal $\varepsilon$. In contrast, even under the same separation condition, no radius-independent additive weak coreset bound exists in the Euclidean plane for $k=2$.
作者备注：We extend the previous results with a strong coreset guarantee, improved lower bounds, tight bounds for well-separated clusters, and a separation between hyperbolic and Euclidean additive coresets