January 01, 1970
We construct coresets for the continuous \(k\)-center problem in fixed-dimensional hyperbolic space \(\mathbb{H}^D\). The input is a set \(P\) of \(n\) points in \(\mathbb{H}^D\), where \(D=O(1)\), and the centers may be placed anywhere in the ambient hyperbolic space. Given \(\varepsilon\in(0,1)\), we construct a subset \(P_\varepsilon\subseteq P\) such that every optimal continuous \(k\)-center solution for \(P_\varepsilon\) is a \((1+\varepsilon)\)-approximation for \(P\).
The main difficulty is the exponential volume growth of hyperbolic balls, which prevents a direct grid-based coreset from having size independent of the input radius. We overcome this by dividing the construction according to the farthest-first scale. At bounded scales, we use local Euclidean grids in the Poincaré ball model. At intermediate scales, we use an anchor-centered shell–cone decomposition together with exact distance profiles obtained from the hyperbolic law of cosines. At large scales, we avoid discretizing the ambient ball and instead keep input witnesses indexed by coarse profiles of the induced \(k\)-center distance functions on each shell–cone bucket.
The resulting coreset has size \(\left(1/\varepsilon\right)^{O(kD)}\) and can be constructed in time \(O(nk\left(1/\varepsilon\right)^{O(kD)}).\) Both bounds are independent of the input radius, and the coreset size is also independent of \(n\). Consequently, for fixed \(D\), \(k\), and \(\varepsilon\), this gives a linear-time construction of a constant-size coreset for the continuous \(k\)-center problem in hyperbolic space.
The \(k\)-center problem is one of the most fundamental optimization problems in computational geometry and clustering. Given a dataset \(P\) consisting of \(n\) points and an integer \(k\), the goal is to choose \(k\) centers so that all input points are covered within the smallest possible distance to their nearest center. More precisely, for a center set \(C\), define \[\Phi_P(C)=\max_{p\in P}\min_{c\in C} d(p,c)\] The objective is to find a set \(C\) of size \(k\) that minimizes this maximum assignment distance. Since examining all possible center sets by brute force requires prohibitively large running time, an important research goal is to design efficient approximation algorithms or to reduce the original input to a small representative subset and solve the problem on that reduced instance.
In fixed-dimensional Euclidean space, Agarwal and Procopiuc [1] gave a \((1+\varepsilon)\)-approximation algorithm for the Euclidean \(k\)-center problem. Their algorithm first computes a constant-factor estimate \(\sigma_0\) of the optimal radius and overlays the space with a grid whose mesh size is proportional to \(\varepsilon\sigma_0\). It then constructs a finite set \(P'\) of grid points adjacent to cells containing input points. The set \(P'\) has size \(|P'|=O\left( k/\varepsilon^D \right)\) which depends only on \(k\), \(D\), and \(\varepsilon\), and is independent of the number \(n\) of input points. An optimal \(k\)-center solution is then computed on \(P'\), and the radii of the resulting balls are enlarged by a controlled additive amount so that they cover the original input. This yields a \((1+\varepsilon)\)-approximation in time \(O(Dn\log k) + (k/\varepsilon)^{O(k^{1-1/D})}\).
Hyperbolic geometry has received considerable attention in representation learning, where Poincaré and Lorentz embeddings are used to represent large-scale hierarchical and tree-like data [2], [3]. More directly related to clustering, recent methods optimize continuous embeddings in hyperbolic space and exploit the resulting geometry to recover hierarchical cluster structures or define intrinsic distances for hierarchical data [4], [5]. As the resulting hyperbolic data sets may be large, these developments motivate the design of efficient clustering algorithms and compact summaries, such as coresets, that operate directly in the intrinsic hyperbolic metric.
Nevertheless, compared with the extensive literature on Euclidean and general metric clustering [6]–[9], the algorithmic study of clustering in hyperbolic space remains limited [10], [11]. Several other computational problems have been studied in hyperbolic and Gromov hyperbolic spaces, including diameters and radii, nearest-neighbor and farthest-neighbor searching, and tree approximations [12]–[16]. To the best of our knowledge, no previous work has studied coresets for the \(k\)-center problem in hyperbolic space.
In this paper, we construct a coreset \(P_{\varepsilon} \subseteq P\) for the continuous \(k\)-center problem in fixed-dimensional hyperbolic space. We guarantee that an optimal continuous \(k\)-center solution computed on \(P_\varepsilon\) gives a \((1+\varepsilon)\)-approximate solution for the original input \(P\). Our construction yields a coreset of size \(O(k/\varepsilon^D)\) in the bounded-scale case and \((1/\varepsilon)^{O(kD)}\) in the large-scale case. These bounds are independent of both the input size \(n\) and the radius of the input point set. For fixed \(D\), \(k\), and \(\varepsilon\), the coreset can be constructed in \(O(n)\) time. Since the standard models of hyperbolic space are mutually isometric, we may choose the most convenient one without changing any metric property. Throughout this paper, we use the Poincaré ball model \((\mathbb{B}^D,d_H)\), where \(\mathbb{B}^D\) is the open unit ball in \(\mathbb{R}^D\) centered at the origin \(O\), and \(d_H\) is the hyperbolic metric. (See Section 2.2 for a more detailed introduction to the Poincaré ball model.)
We assume throughout that the dimension \(D\) is fixed, that is, \(D=O(1)\), and that \(\varepsilon \in (0,1)\). Let \(P\) be a set of \(n\) points in the Poincaré ball model \(\mathbb{B}^D\) of the \(D\)-dimensional hyperbolic space \(\mathbb{H}^D\). For any center set \(C \subset \mathbb{H}^D\) with \(|C| \le k\), define \[d_H(p,C) = \min_{c\in C} d_H(p,c), \qquad \Phi_P(C) = \max_{p\in P} d_H(p,C).\] The optimal continuous \(k\)-center radius of \(P\) is \[\operatorname{OPT}_k (P) =\min_{\substack{C\subset\mathbb{H}^D\\ |C|\le k}} \Phi_P(C).\] We show how to construct a coreset \(P_\varepsilon \subseteq P\) such that every optimal solution \(C_\varepsilon\) to the continuous \(k\)-center problem on \(P_\varepsilon\), that is, \[C_\varepsilon \in \mathop{\mathrm{arg\,min}}_{\substack{C\subseteq\mathbb{H}^D\\ |C|\le k}} \Phi_{P_\varepsilon}(C)\] satisfies \[\Phi_P(C_\varepsilon) \le (1+\varepsilon) \operatorname{OPT}_k (P).\] Thus, solving the continuous \(k\)-center problem on the reduced instance \(P_\varepsilon\) yields a \((1+\varepsilon)\)-approximate solution for the original instance \(P\).
The construction depends on the farthest-first scale \(R_G=\Phi_P(A_k)\), where \(A_k\) is the set of \(k\) anchors computed by Gonzalez’s farthest-first traversal. In the bounded-scale case, it yields a coreset of size \(O\left({k}/{\varepsilon^D}\right).\) In the intermediate-scale case, we use the shell–cone representative scheme with exact distance profiles based on the hyperbolic law of cosines, obtaining a coreset of size \(\left(1/\varepsilon\right)^{O(kD)}.\) In the large-scale case, the construction produces a coreset satisfying \(|P_\varepsilon| \le O\left( k\left(1/\varepsilon\right)^{O(kD)} \right).\) In all cases, the construction time is \(O\left( nk\left(1/\varepsilon\right)^{O(kD)} \right).\) The coreset-size bounds are independent of both the input size \(n\) and any enclosing radius of the input point set. Consequently, for fixed \(D\), \(k\), and \(\varepsilon\), the coreset has constant size and can be constructed in \(O(n)\) time.
Theorem 1 (Continuous \(k\)-center coreset in hyperbolic space). Let \(D\ge 1\), let \(0<\varepsilon<1\), and let \(P\subseteq\mathbb{B}^D\) be a finite set of \(n\) points. Then one can construct an input subset \(P_\varepsilon\subseteq P\) such that every optimal continuous \(k\)-center solution \[C_{P_\varepsilon} \in \operatorname*{argmin}_{\substack{C\subseteq\mathbb{H}^D\\ |C|\le k}} \Phi_{P_\varepsilon}(C)\] satisfies \[\Phi_P(C_{P_\varepsilon}) \le (1+\varepsilon)\operatorname{OPT}_k(P).\] Moreover, \[|P_\varepsilon| = \left(\frac{1}{\varepsilon}\right)^{O(kD)},\] and the construction time is \[O\left( nk\left(\frac{1}{\varepsilon}\right)^{O(kD)} \right).\] Consequently, for fixed \(D\), \(k\), and \(\varepsilon\), the coreset has constant size and can be constructed in \(O(n)\) time.
Our construction begins by computing \(k\) farthest-first anchors \[A_k=\{a_1,\ldots,a_k\}\subseteq P\] using Gonzalez’s farthest-first traversal [17], together with their covering radius \(R_G=\Phi_P(A_k)\). By maintaining, for every input point, its distance to the nearest selected anchor, both \(A_k\) and \(R_G\) can be computed in \(O(kn)\) time. The radius \(R_G\) provides a constant-factor estimate of the optimal continuous \(k\)-center radius: \[\operatorname{OPT}_k (P) \le R_G \le 4\operatorname{OPT}_k (P).\]
We divide the construction into three scale regimes. Let \(R_0>0\) be the bounded-scale threshold, chosen independently of \(n\), \(k\), \(D\), and \(\varepsilon\). Let \[R_1=\frac{16C_\eta}{\varepsilon},\] where \(C_\eta\) is the absolute constant appearing in the large-scale profile error bound. After increasing \(C_\eta\) if necessary, we may assume that \(R_0 < R_1\) for all \(0<\varepsilon<1\). The three regimes are \[0\le R_G\le R_0, \qquad R_0 \le R_G \le R_1, \qquad R_G\ge R_1.\]
In the bounded-scale regime \(R_G\le R_0\), we map each farthest-first anchor to the origin of the Poincaré ball and apply a local Euclidean grid to its assigned cluster. Since the hyperbolic and Euclidean metrics are uniformly comparable on bounded-radius balls, retaining one input point from each occupied grid cell gives an \(O(\varepsilon R_G)\)-representative subset. A metric-transfer argument then converts this additive error into a multiplicative \((1+\varepsilon)\)-approximation, yielding a coreset of size \(O(k/\varepsilon^D)\).
In the intermediate-scale regime \(R_0 \le R_G \le R_1\), the same anchor-centered shell–cone decomposition is used. However, the coarse large-scale distance profile is not yet accurate enough, because its absolute additive constants cannot be absorbed directly into \(O(\varepsilon R_G)\). We therefore replace the coarse profile approximation by an exact-profile discretization based on the hyperbolic law of cosines. This gives the same type of shell–cone representative set, with additive error \(O(\varepsilon R_G)\), and yields a coreset of size \(\left(1/\varepsilon\right)^{O(kD)}.\)
In the large-scale regime \(R_G\ge R_1\), a direct grid would require exponentially many cells because of the exponential volume growth of hyperbolic balls. We therefore partition the input around the farthest-first anchors into radial shells and angular cones. For each resulting bucket, we retain a finite set of input witnesses indexed by coarse profiles of the \(k\) center-distance functions. These profiles capture the points that may determine the maximum distance for a relevant center configuration, without discretizing the entire ambient ball. This yields a coreset of size \((1/\varepsilon)^{O(kD)}\) that is independent of \(R_G\).
Remark 2. The exact numerical values of the scale thresholds are not important. The constant \(R_0>0\) is a fixed bounded-scale threshold, independent of \(n\), \(k\), \(D\), and \(\varepsilon\). The large-scale threshold \[R_1=\frac{16C_\eta}{\varepsilon}\] is chosen so that the absolute additive error in the large-scale profile approximation can be absorbed into the final multiplicative \((1+\varepsilon)\)-error. These thresholds only separate the bounded, intermediate, and large-scale regimes and are not intended to be sharp.
In an arbitrary metric space, Gonzalez’s farthest-first traversal [17] computes a \(2\)-approximation for the discrete \(k\)-center problem in \(O(kn)\) time. This approximation factor is best possible for general metric \(k\)-center in polynomial time unless \(\mathrm{P}=\mathrm{NP}\) [18]. However, our setting is the continuous \(k\)-center problem, in which centers may be placed anywhere in the ambient space. Since the optimal discrete radius is at most twice the optimal continuous radius, the farthest-first anchor set \(A_k\subseteq P\) satisfies \(\operatorname{OPT}^{\mathrm{cont}}_k (P) \le \Phi_P(A_k) \le 4\operatorname{OPT}^{\mathrm{cont}}_k (P)\). We use this \(4\)-approximate radius only as a computable reference scale for the coreset construction.
The hardness of improving the factor \(2\) applies to arbitrary metric spaces and therefore does not preclude stronger approximation guarantees in geometrically structured spaces. In fixed-dimensional Euclidean space, Agarwal and Procopiuc developed exact and approximation algorithms for the continuous \(k\)-center problem, including a \((1+\varepsilon)\)-approximation scheme with running time \(O(n\log k)+\left(k/{\varepsilon}\right)^{O\left(k^{1-1/D}\right)}\) up to dimension-dependent factors [1]. Blank et al. [19] recently established fine-grained lower bounds for the continuous Euclidean \(k\)-center problem. Under the Exponential Time Hypothesis, they showed that the exact problem admits no algorithm with running time \(f(k) n^{o\left(k^{1-1/D}\right)}\). They also ruled out a \((1+\varepsilon)\)-approximation algorithm with running time \(\left(k/{\varepsilon}\right)^{o\left(k^{1-1/D}\right)}n^{O(1)}\). Thus, the dependence on \(k\) and \(\varepsilon\) in the algorithm of Agarwal and Procopiuc is essentially optimal under these assumptions.
A variety of algorithmic problems have also been studied in Gromov-hyperbolic metric spaces and negatively curved spaces. Chepoi et al. [12] obtained linear-time additive approximations for diameters, radii, and eccentricities in geodesic \(\delta\)-hyperbolic spaces and graphs, while Krauthgamer and Lee [13] developed general algorithmic tools for negatively curved spaces. Other work has considered center-type optimization problems in Gromov-\(\delta\)-hyperbolic graphs and related graph metrics [11]. These results primarily exploit coarse tree-like structure and typically provide constant or \(O(\delta)\)-additive guarantees. However, they do not construct coresets for the continuous \(k\)-center problem in hyperbolic space, where centers may be placed anywhere in the ambient space \(\mathbb{H}^D\).
Recent developments in hyperbolic Steiner spanners have underscored the necessity of partitioning hyperbolic space into distinct scale-dependent regimes. Kisfaludi-Bak and van Wordragen [20] distinguish between local Euclidean-like behaviors and global tree-like structures, identifying the intermediate distance range as particularly challenging to manage. While our work focuses on coresets for the continuous \(k\)-center problem rather than spanners, we observe an architectural phenomenon where the transition range \(R_0 \le R_G \le R_1 = O(1/\varepsilon)\) remains uncovered by standard bounded or large-scale arguments. To address this, we introduce an exact-profile discretization method derived from the hyperbolic law of cosines, ensuring robust approximation guarantees across all scale regimes.
Coresets have been used extensively to reduce the size of geometric clustering instances. In Euclidean space, grid-based and representative-set constructions yield small summaries for \(k\)-center and related extent problems, while weighted coresets have been developed for \(k\)-median, \(k\)-means, and more general clustering objectives [8], [21], [22]. Such coresets allow the original optimization problem to be solved on a reduced instance whose size depends on the dimension, the number of centers, and the approximation parameter, rather than on \(n\). However, the standard Euclidean grid argument does not yield a radius-independent coreset in \(\mathbb{H}^D\). Indeed, a uniform discretization of a hyperbolic ball of radius \(R\) may require a number of cells that grows exponentially with \(R\). The main purpose of our large-scale shell-cone construction is to overcome precisely this obstruction.
Our bounded-scale construction is inspired in part by the local-grid approach of Park and Vigneron [16] for farthest-point problems in hyperbolic space. In both settings, an isometry maps a suitable reference point to the origin of the Poincaré ball, after which the local comparability of the hyperbolic and Euclidean metrics permits a Euclidean discretization. The two problems are nevertheless fundamentally different. A farthest-point coreset must preserve, for every query point \(q\), the single maximum \(\max_{p\in P} d_H(q,p)\), whereas the continuous \(k\)-center problem requires optimizing the lower-envelope objective \(\max_{p\in P}\min_{c\in C} d_H(p,c)\) over all center sets \(C\) of size at most \(k\). Consequently, in the large-scale regime, retaining one radial extreme point from each cone is not sufficient. The relevant representative point within a shell-cone bucket depends on the joint configuration of all \(k\) centers. Our construction therefore introduces a coarse distance-signature scheme for selecting such representative points, which has no direct counterpart in the farthest-point setting.
Let \((X,d)\) be a metric space and let \(P \subset X\) be finite. For \(p\in X\) and \(C \subset X\), define \[d(p,C)=\min_{c\in C}d(p,c),\] and for a finite center set \(C \subset X\), define its covering cost on \(P\) by \[\Phi_P(C)=\max_{p\in P}d(p,C).\] The continuous \(k\)-center optimum is \[\mathrm{OPT}_k^{\mathrm{cont}}(P) = \min_{\substack{C\subset X\\ |C|\le k}} \Phi_P(C).\] Here, continuous means that the centers may be chosen anywhere in the ambient metric space, rather than being restricted to the input set.
Throughout the remainder of the paper, we take \(X=\mathbb{H}^D\) and \(d=d_H\), and write \[\mathrm{OPT}_k(P)=\mathrm{OPT}_k^{\mathrm{cont}}(P).\] For \(a \in \mathbb{H}^D\) and \(R \ge 0\), let \[B_H(a,R)=\{x \in \mathbb{H}^D:d_H(a,x)\le R\}\] denote the closed hyperbolic ball of radius \(R\) centered at \(a\).
We work in the Poincaré ball model of \(D\)-dimensional hyperbolic space of constant curvature \(-1\). In this model, \[\mathbb{B}^{D}=\{x\in\mathbb{R}^D:|x|<1\},\] and the hyperbolic distance between \(x,y\in\mathbb{B}^{D}\) is \[d_H(x,y) = \mathop{\mathrm{arcosh}}\left(1+\frac{2\|x-y\|^2}{(1-\|x\|^2)(1-\|y\|^2)}\right).\] In particular, \[d_H(0,x)=\log \left(\frac{1+\|x\|}{1-\|x\|}\right)=2\mathop{\mathrm{artanh}}|x|.\] We will repeatedly change the origin of the model. For every \(a\in\mathbb{B}^{D}\), there exists a hyperbolic isometry \(\mu_a:\mathbb{B}^{D}\to\mathbb{B}^{D}\) such that \(\mu_a(a)=0\). Hence, for all \(x,y\in\mathbb{B}^{D}\), \[d_H(x,y)=d_H\bigl(\mu_a(x),\mu_a(y)\bigr).\] Thus, when analyzing the points assigned to an anchor \(a\), we may first apply \(\mu_a\) and assume without loss of generality that the anchor is the origin. For fixed \(D\), the map \(\mu_a\) and the distance \(d_H\) can be evaluated in constant time in the real-RAM model. For background on the Poincaré ball model and hyperbolic isometries, we refer the reader to [23] and to [16].
Fix a sufficiently large absolute constant \(R_0>0\), independent of \(n\), \(k\), \(D\), and \(\varepsilon\). In this section, we consider the bounded-scale regime \(R_G\le R_0\). We compute \(k\) farthest-first anchors, assign every input point to a nearest anchor, and apply a local Euclidean grid separately to each resulting cluster.
Let \(P=\{p_1,\ldots,p_n\}\subset\mathbb{B}^{D}\). Run Gonzalez’s farthest-first traversal [17] for \(k\) steps, and let \(A_k=\{a_1,\ldots,a_k\}\subseteq P\) be the resulting anchor set. Define its covering radius by \[R_G=\Phi_P(A_k)=\max_{p\in P}d_H(p,A_k).\] Assign each point \(p\in P\) to a nearest anchor, breaking ties arbitrarily but consistently, and let \(P_i\) denote the cluster assigned to \(a_i\). Thus, \[P=P_1\mathbin{\dot{\cup}}\cdots\mathbin{\dot{\cup}}P_k.\]
Lemma 1. The farthest-first radius satisfies \(\mathrm{OPT}_k(P)\le R_G\le 4\mathrm{OPT}_k(P)\). Moreover, for every \(i\in\{1,\ldots,k\}\), \(P_i\subseteq B_H(a_i,R_G)\). Consequently, if \(\mu_{a_i}\) is an isometry satisfying \(\mu_{a_i}(a_i)=O\), then \[\mu_{a_i}(P_i) \subseteq B_H(O,R_G) \subseteq B_H(O,R_0).\]
Proof. Since \(A_k\) is a feasible set of \(k\) continuous centers, \(\mathrm{OPT}_k(P) \le \Phi_P(A_k)=R_G\). Gonzalez’s traversal gives a \(2\)-approximation for the discrete \(k\)-center problem. Moreover, the optimal discrete \(k\)-center radius is at most twice the optimal continuous radius. Therefore, \[R_G \le 2\mathrm{OPT}_k^{\mathrm{disc}}(P) \le 4\mathrm{OPT}_k(P).\] For every \(p\in P_i\), the nearest-anchor assignment gives \[d_H(p,a_i) = d_H(p,A_k) \le \Phi_P(A_k) = R_G.\] Hence, \(P_i\subseteq B_H(a_i,R_G).\) Since \(\mu_{a_i}\) is an isometry and \(\mu_{a_i}(a_i)=O\), for every \(p\in P_i\), \[\begin{align} d_H\bigl(O,\mu_{a_i}(p)\bigr) &= d_H\bigl(\mu_{a_i}(a_i),\mu_{a_i}(p)\bigr) \\ &= d_H(a_i,p) \\ &\le R_G. \end{align}\] Thus, \(\mu_{a_i}(P_i)\subseteq B_H(O,R_G).\) The final inclusion follows from \(R_G\le R_0\). ◻
Let \(\rho_0=\tanh(R_0/2)\) and define \[L_0=\frac{2}{1-\rho_0^2}=2\cosh^2(R_0/2)=1+\cosh R_0.\] Since \(R_0\) is an absolute constant, \(L_0\) is also an absolute constant.
Lemma 2. For any \(x,y\in B_H(O,R_0)\), \[2\|x-y\| \le d_H(x,y) \le L_0\|x-y\|.\]
Proof. In the Poincaré ball model, the hyperbolic length element is \[ds_H = \frac{2|dz|}{1-|z|^2}.\] Let \(\gamma\) be a hyperbolic geodesic joining \(x\) and \(y\). Since \(1-|z|^2\le1\), we have \[d_H(x,y) =\int_\gamma \frac{2|dz|}{1-|z|^2} \ge 2\int_\gamma|dz| \ge 2\|x-y\|.\] For the upper bound, \(B_H(O,R_0)\) is the Euclidean ball centered at \(O\) with radius \(\rho_0\). Hence the Euclidean segment \(\overline{xy}\) is contained in this ball. Since hyperbolic distance is at most the hyperbolic length of any curve joining \(x\) and \(y\), \[d_H(x,y) \le \int_{\overline{xy}} \frac{2|dz|}{1-|z|^2} \le \frac{2}{1-\rho_0^2} \int_{\overline{xy}}|dz| = L_0\|x-y\|.\] ◻
Assume first that \(R_G>0\), and define the grid mesh by \(h = {\varepsilon R_G}/{4L_0\sqrt D}.\) Let \(\mathcal{G}_h=h\mathbb{Z}^D\) be the regular Euclidean grid with cell side length \(h\).
Lemma 3. Let \(x,y\in B_H(O,R_0)\) lie in the same cell of \(\mathcal{G}_h\). Then \[d_H(x,y) \le \frac{\varepsilon R_G}{4}.\]
Proof. If \(x\) and \(y\) lie in the same grid cell, then the difference between their corresponding coordinates is at most \(h\). Consequently, \(\|x-y\| \le h \sqrt D\). By Lemma 2, \[d_H(x,y) \le L_0\|x-y\| \le L_0 h \sqrt D = \frac{\varepsilon R_G}{4}.\] ◻
For each cluster \(P_i\), apply the isometry \(\mu_{a_i}\) sending \(a_i\) to \(O\). By Lemma 1, \[\mu_{a_i}(P_i) \subseteq B_H(O,R_G) \subseteq B_H(O,R_0).\] Partition \(\mu_{a_i}(P_i)\) using the grid \(\mathcal{G}_h\), and retain one original input point from every occupied grid cell. Let \(P_{\varepsilon_i}\subseteq P_i\) denote the retained subset, and set \(P_{\varepsilon}=\bigcup_{i=1}^k P_{\varepsilon_i}.\)
If \(R_G=0\), every input point has distance zero from some anchor. In this case, we take \(P_{\varepsilon}\) to be the set of distinct anchors, which is an exact coreset.
Theorem 3. Assume that \(0<R_G\le R_0\), and construct \(P_{\varepsilon}\subseteq P\) as above. Let \[C_{P_{\varepsilon}} \in \mathop{\mathrm{arg\,min}}_{\substack{C\subseteq\mathbb{H}^{D}\\ |C|\le k}} \Phi_{P_{\varepsilon}}(C)\] be an optimal continuous \(k\)-center solution for \(P_{\varepsilon}\). Then \(\Phi_P(C_{P_{\varepsilon}}) \le (1+\varepsilon)\mathrm{OPT}_k (P).\)
Proof. For every \(p \in P_{i}\), let \(\pi(p) \in P_{\varepsilon_i}\) be the original input point retained from the same grid cell as \(\mu_{a_i}(p)\). By Lemma 3 and the invariance of hyperbolic distance under the isometry \(\mu_{a_i}\), we have \[d_H\bigl(p,\pi(p)\bigr) \le \frac{\varepsilon R_G}{4}.\] Let \(C \subseteq \mathbb{H}^{D}\) be any center set with \(|C| \le k\). For every \(p\in P\), the triangle inequality gives \[d_H(p,C) \le d_H\bigl(p,\pi(p)\bigr)+d_H\bigl(\pi(p),C\bigr) \le \frac{\varepsilon R_G}{4}+\Phi_{P_\varepsilon}(C).\] Taking the maximum over all \(p\in P\), we obtain \[\label{eq:transfer} \Phi_P(C) \le \Phi_{P_\varepsilon}(C)+\frac{\varepsilon R_G}{4}.\tag{1}\] Let \(C^\star\) be an optimal continuous \(k\)-center solution for \(P\). Since \({P_\varepsilon} \subseteq P\), we have \[\Phi_{P_\varepsilon}(C^\star) \le \Phi_P(C^\star) = \mathrm{OPT}_k(P).\] By the optimality of \(C_{P_\varepsilon}\) on \(P_\varepsilon\), \[\Phi_{P_\varepsilon}(C_{P_\varepsilon}) \le \Phi_{P_\varepsilon}(C^\star) \le \mathrm{OPT}_k (P).\] Applying inequality 1 with \(C=C_{P_\varepsilon}\), we obtain \[\Phi_P(C_{P_\varepsilon}) \le \mathrm{OPT}_k(P) + \frac{\varepsilon R_G}{4}.\] Finally, Lemma 1 gives \[\frac{\varepsilon R_G}{4} \le \varepsilon\mathrm{OPT}_k(P).\] Therefore, \[\Phi_P(C_{P_\varepsilon}) \le (1+\varepsilon)\mathrm{OPT}_k(P).\] ◻
Fix a cluster \(P_i\). After moving its anchor to the origin, the transformed cluster is contained in the Euclidean ball of radius \(\rho_G=\tanh(R_G/2)\), and hence in a Euclidean cube of side length \(2\rho_G\). Therefore, the number of grid cells of side length \(h\) intersecting this cube is \[O\left( \left( 1+\frac{\rho_G}{h} \right)^D \right).\] Since the construction retains at most one input point from each occupied cell, the number of representatives selected from \(P_i\) satisfies \[|P_{\varepsilon_i}|=O\left(\left(1+\frac{\rho_G}{h}\right)^D\right).\] Using \(h={\varepsilon R_G}/{4L_0\sqrt D}\), we obtain \[\frac{\rho_G}{h}=\frac{4L_0\sqrt D}{\varepsilon} \frac{\rho_G}{R_G}.\] Moreover, \(\rho_G=\tanh(R_G/2) \le {R_G}/{2}\), and consequently \[\frac{\rho_G}{h} \le \frac{2L_0\sqrt D}{\varepsilon}.\] Because \(D\) is fixed and \(R_0\) is an absolute constant, the quantity \(L_0=1+\cosh R_0\) is constant. It follows that \[|P_{\varepsilon_i}|=O\left(\frac{1}{\varepsilon^D}\right).\] Summing over the \(k\) anchor clusters gives \[|P_\varepsilon| \le \sum_{i=1}^k |P_{\varepsilon_i}|=O\left(\frac{k}{\varepsilon^D}\right).\] Consequently, for fixed \(D\), \(k\), and \(\varepsilon\), the coreset \(P_\varepsilon\) has constant size independent of the number \(n\) of input points.
Gonzalez’s farthest-first traversal maintains the distance from each input point to its nearest selected anchor. Each iteration scans all \(n\) input points and selects the point with the largest maintained distance as the next anchor. Repeating this process \(k\) times computes the anchor set \(A_k\) in \(O(kn)\) time. The same maintained distances determine the covering radius \(R_G\) and the nearest-anchor assignment within the same running time.
For each cluster \(P_i\), applying the isometry \(\mu_{a_i}\) to a point and determining the grid cell containing its image take \(O(1)\) time for fixed \(D\). The grid cells can be indexed by integer coordinate vectors, and the number of relevant cells for each cluster is \(O\left({1}/{\varepsilon^D}\right)\) by the coreset-size analysis above. Thus, initializing the grid structure and scanning all points in \(P_i\) take \[O\left(|P_i|+\frac{1}{\varepsilon^D}\right)\] time. Summing over all \(k\) clusters, the local-grid step requires \[O\left(n+\frac{k}{\varepsilon^D}\right)\] time. Therefore, the total construction time is \[O\left(kn+n+\frac{k}{\varepsilon^D}\right).\] In particular, for fixed \(D\), \(k\), and \(\varepsilon\), the bounded-scale coreset can be constructed in \(O(n)\) time. The preceding arguments are summarized in the following theorem.
Theorem 4 (Bounded-scale continuous \(k\)-center coreset). Let \(D\ge 1\), let \(0<\varepsilon<1\), and let \(P \subset \mathbb{B}^{D}\) be finite. Run Gonzalez’s farthest-first traversal for \(k\) steps, and let \[A_k=\{a_1,\ldots,a_k\}, \qquad R_G=\Phi_P(A_k).\] Assume that \(R_G\le R_0,\) where \(R_0>0\) is a fixed absolute constant. Then one can construct an input subset \(P_\varepsilon\subseteq P\) such that every optimal continuous \(k\)-center solution \(C_{P_\varepsilon}\) for \(P_\varepsilon\) satisfies \[\Phi_P(C_{P_\varepsilon}) \le (1+\varepsilon)\mathrm{OPT}_k (P).\] Moreover, \[|P_\varepsilon|=O\left(\frac{k}{\varepsilon^D}\right),\] and the construction time is \[O\left( kn+n+\frac{k}{\varepsilon^D}\right).\] Consequently, for fixed \(D\), \(k\), and \(\varepsilon\), the coreset can be constructed in \(O(n)\) time.
We now consider the regime in which the farthest-first scale \(R_G\) is large. A direct grid discretization of the hyperbolic ball \(B_H(a_i,R_G)\) would require exponentially many cells in \(R_G\), because hyperbolic balls have exponential volume growth. We therefore do not discretize the ambient ball. Instead, we decompose each farthest-first cluster into radial shells and angular cones and discretize only the effect of a center on each resulting bucket.
For simplicity, the shell–cone construction is described for \(D \ge 2\). For \(D=1\), all statements below are interpreted with the angular cover replaced by the two-point sphere \(S^0\), and the angular-record count \(O(1/\varepsilon)^{D-1}\) replaced by \(O(1)\). The same proofs then reduce to the radial decomposition.
Throughout this section, let \(A_k=\{a_1,\ldots,a_k\}\) be the farthest-first anchor set, let \(R_G=\Phi_P(A_k)\), and let \(P=P_1\mathbin{\dot{\cup}}\cdots\mathbin{\dot{\cup}}P_k\) be the nearest-anchor partition. Thus \(P_i\subseteq B_H(a_i,R_G)\) for every \(i\).
For each anchor \(a_i\), let \(\mu_{a_i}:\mathbb{H}^D\longrightarrow\mathbb{H}^D\) be an isometry satisfying \(\mu_{a_i}(a_i)=O\). For every \(p\in P_i\setminus\{a_i\}\), write \(x_i(p)=\mu_{a_i}(p)\). Since \(x_i(p)\neq O\), it has a Euclidean polar representation \[x_i(p)=\|x_i(p)\|\xi_i(p),~\xi_i(p)\in\mathbb{S}^{D-1}.\] Moreover, in the Poincaré ball model, \(d_H(O,x_i(p))=2\operatorname{arctanh}\|x_i(p)\|.\) Thus, if \(r_i(p)=d_H(a_i,p)=d_H(O,x_i(p)),\) then \(\|x_i(p)\|=\tanh\left({r_i(p)}/{2}\right).\) Consequently, \(\mu_{a_i}(p)=\tanh\left({r_i(p)}/{2}\right)\xi_i(p).\) Here \[r_i(p)\in(0,R_G],\qquad \xi_i(p)\in\mathbb{S}^{D-1}.\] Thus \(r_i(p)\) and \(\xi_i(p)\) are the radial and angular coordinates of \(p\) around \(a_i\).
Fix a sufficiently small absolute constant \(\alpha>0\), to be chosen later. Put \(\Delta=\alpha\varepsilon R_G.\) Let \[J=\left\lceil\frac{R_G}{\Delta}\right\rceil-1.\] For \(0\le j<J\), define \[I_j=[j\Delta,(j+1)\Delta),\] and define the last interval by \[I_J=[J\Delta,R_G].\] Choose a family \(\mathcal{U}=\{U_1,\ldots,U_{M}\}\) of subsets of \(\mathbb{S}^{D-1}\) having angular diameter at most \(\alpha\varepsilon\) and covering \(\mathbb{S}^{D-1}\). Standard sphere-net bounds give \[M=O\left(\left(\frac{1}{\alpha\varepsilon}\right)^{D-1}\right).\]
Definition 1. For \(i,j,\ell\), define \[B(i,j,\ell)=\left\{p\in P_i \setminus A_k: r_i(p)\in I_j, ~\xi_i(p)\in U_\ell \right\}.\] A nonempty set of this form is called a shell–cone bucket.
Lemma 4. The number of nonempty shell–cone buckets is \[O\left(k\left(\frac{1}{\varepsilon}\right)^D\right),\] where the multiplicative constant depends only on \(D\) and the fixed choice of \(\alpha\).
Proof. For every \(p\in P_i\), we have \(0\le r_i(p)\le R_G\). Hence the number of radial intervals for one anchor is \[\left\lceil\frac{R_G}{\Delta}\right\rceil=\left\lceil\frac{1}{\alpha\varepsilon}\right\rceil=O\left(\frac{1}{\varepsilon}\right),\] because \(\alpha\) is an absolute constant. The number of angular sets is \[M=O\left(\left(\frac{1}{\alpha\varepsilon}\right)^{D-1}\right)=O\left( \left(\frac{1}{\varepsilon}\right)^{D-1}\right).\] Therefore, for one anchor, the number of shell–cone buckets is at most \[O\left(\frac{1}{\varepsilon}\right) \cdot O\left(\left(\frac{1}{\varepsilon}\right)^{D-1}\right)=O\left( \left(\frac{1}{\varepsilon}\right)^D\right).\] Summing over the \(k\) anchors gives \[O\left(k\left(\frac{1}{\varepsilon}\right)^D\right)\] shell–cone buckets. ◻
Fix \(i\in\{1,\ldots,k\}\), and let \(B\) be a nonempty shell–cone bucket associated with the anchor \(a_i\). For notational simplicity, write \(a:=a_i.\) We first identify the centers that can affect the lower envelope on \(B\). We then describe the large-scale form of the corresponding one-center distance profiles and show that these profiles admit a finite discretization with controlled additive error.
The distance-profile construction does not need to represent all possible centers in \(\mathbb{H}^D\). It is sufficient to consider centers that can be nearest to a point in a bucket for some center set that covers the anchors at scale \(R_G\).
Definition 2. A center set \(C\subseteq\mathbb{H}^D\), with \(|C|\le k\), is said to cover the anchors at scale \(R_G\) if \[\Phi_{A_k}(C)=\max_{a\in A_k}d_H(a,C) \le R_G.\]
Lemma 5. Let \(C\) cover the anchors at scale \(R_G\). Let \(p\in P_i\), and let \(c\in C\) be a nearest center to \(p\). Then \[d_H(a_i,c)\le 3R_G.\]
Proof. Since \(p\in P_i\), the nearest-anchor assignment gives \(d_H(p,a_i)\le R_G.\) Since \(C\) covers the anchors at scale \(R_G\), we also have \(d_H(a_i,C)\le R_G.\) Therefore, \(d_H(p,C) \le d_H(p,a_i)+d_H(a_i,C) \le 2R_G.\) Because \(c\) is a nearest center to \(p\), \(d_H(p,c)=d_H(p,C)\le 2R_G.\) Hence, by the triangle inequality, \[d_H(a_i,c) \le d_H(a_i,p)+d_H(p,c) \le 3R_G.\] ◻
Apply the isometry \(\mu_a\) sending \(a\) to the origin \(O\), and write \(\mu_a(u)=(r,\xi)\) and \(\mu_a(c)=(s,\zeta)\) in polar coordinates around \(O\). Thus \(r=d_H(a,u),~s=d_H(a,c),~\theta=\angle(\xi,\zeta).\) When \(s=0\), the direction \(\zeta\) may be chosen arbitrarily, since all the expressions below are then independent of \(\zeta\). For every center \(c\) that is nearest to at least one point of \(B\), Lemma 5 gives \(0\le s\le 3R_G.\) The next two elementary lemmas make this large-scale distance profile precise. We show that the four exponential terms in the hyperbolic cosine law reduce, up to absolute constants, to one radial scale and one transverse angular scale.
Lemma 6. For every \(x\ge 1\), \[\operatorname{arcosh}x \le \log(2x).\]
Proof. By the definition of the inverse hyperbolic cosine, \[\operatorname{arcosh}x=\log\bigl(x+\sqrt{x^2-1}\bigr), \qquad x\ge 1.\] Since \(x\ge 1\), we have \[0\le \sqrt{x^2-1}\le x.\] Therefore, \[x+\sqrt{x^2-1}\le 2x.\] Taking logarithms gives \[\operatorname{arcosh}x=\log\bigl(x+\sqrt{x^2-1}\bigr) \le \log(2x).\] ◻
Lemma 7. Let \(u=(r,\xi),~c=(s,\zeta)\) be polar coordinates around the same anchor, and put \(\theta=\angle(\xi,\zeta),~d=d_H(u,c).\) For the fixed direction \(\zeta\), define \[\Lambda_\zeta(\xi) = \log\bigl(1-\cos\angle(\xi,\zeta)\bigr), \qquad \Lambda_\zeta(\zeta)=-\infty.\] Then \[\begin{align} &\max\left\{ |r-s|, \; r+s+\Lambda_\zeta(\xi) \right\} -\log 4 \\ &\le d_H(u,c) \\ &\le \max\left\{ |r-s|, \; r+s+\Lambda_\zeta(\xi) \right\} +\log 3 . \end{align}\]
Proof. The hyperbolic law of cosines gives \[\cosh d_H (u,c) = \cosh r\cosh s - \sinh r\sinh s\cos\theta.\] Using \[\cosh t=\frac{e^t+e^{-t}}{2}, \qquad \sinh t=\frac{e^t-e^{-t}}{2},\] we obtain the exact identity \[\begin{align} \label{eq:four-term-proof} 4\cosh d_H (u,c) ={}&e^{r+s}(1-\cos\theta) + e^{r-s}(1+\cos\theta) \notag\\ &+e^{-r+s}(1+\cos\theta) + e^{-r-s}(1-\cos\theta). \end{align}\tag{2}\] Set \[X=e^{|r-s|},\qquad Y=e^{r+s}(1-\cos\theta),\qquad Z=\max\{X,Y\}.\] We first show that the whole four-term expression is controlled, up to absolute constant factors, by the two main scales \(X\) and \(Y\). More precisely, we prove \[Z\le 4\cosh d_H (u,c) \le 6Z.\]
For the lower bound, the first term in 2 gives \[4\cosh d_H (u,c) \ge e^{r+s}(1-\cos\theta) = Y.\] Moreover, since \(r=d_H(a,u)\) and \(s=d_H(a,c)\) for the common anchor \(a\), the reverse triangle inequality gives \[d_H(u,c)\ge \bigl|d_H (a,u) - d_H(a,c)\bigr| = |r-s|.\] Since \(\cosh\) is increasing on \([0,\infty)\), we get \[\cosh d_H (u,c) \ge \cosh |r-s| = \frac{e^{|r-s|}+e^{-|r-s|}}{2} \ge \frac{1}{2} e^{|r-s|} = \frac{1}{2} X.\] Therefore \[4\cosh d_H (u,c) \ge 2X\ge X.\] Combining this with \(4\cosh d_H (u,c) \ge Y\), we obtain \[4\cosh d_H (u,c)\ge \max\{X,Y\}=Z.\]
For the upper bound, use \(0\le 1+\cos\theta\le 2.\) Then the two middle terms in 2 satisfy \[\begin{align} e^{r-s}(1+\cos\theta) + e^{-r+s}(1+\cos\theta) &\le 2(e^{r-s}+e^{s-r}) \\ &\le 4e^{|r-s|} \\ &=4X. \end{align}\] The last term is dominated by the first term because \(r+s\ge 0\), \[e^{-r-s}(1-\cos\theta) \le e^{r+s}(1-\cos\theta) = Y.\] Hence 2 gives \[4\cosh d_H (u,c) \le Y+4X+Y = 4X+2Y \le 6Z.\] Thus we have proved \[Z\le 4\cosh d_H (u,c)\le 6Z.\] Equivalently, \[\frac{Z}{4} \le \cosh d_H (u,c) \le \frac{3}{2} Z.\]
We now convert this comparison for \(\cosh d_H (u,c)\) into a comparison for \(d_H (u,c)\). First, for the lower bound, by the formula \[\operatorname{arcosh}x = \log\bigl(x+\sqrt{x^2-1}\bigr),\qquad x\ge1,\] we have \[\operatorname{arcosh}x\ge \log x.\] Applying this with \(x=\cosh d_H (u,c)\), and using \[\cosh d_H (u,c)\ge \frac{Z}{4},\] we get \[d_H (u,c) = \operatorname{arcosh}(\cosh d_H (u,c)) \ge \log(\cosh d_H (u,c)) \ge \log\frac{Z}{4}=\log Z-\log4.\]
For the upper bound, Lemma 6 gives \[\operatorname{arcosh}x\le \log(2x), \qquad x\ge1.\] Applying this with \(x=\cosh d_H (u,c)\), and using \[\cosh d_H (u,c) \le \frac{3}{2} Z,\] we obtain \[d_H (u,c) = \operatorname{arcosh}(\cosh d_H (u,c)) \le \log(2\cosh d_H (u,c)) \le \log(3Z) = \log Z+\log3.\] It remains to identify \(\log Z\). By definition, \[\begin{align} \log Z &= \log\max\left\{e^{|r-s|},~e^{r+s}(1-\cos\theta)\right\} \\ &=\max\left\{|r-s|,~r+s+\log(1-\cos\theta)\right\}. \end{align}\] Here, when \(\theta=0\), we interpret \[\log(1-\cos\theta)=-\infty,\] so that the second term is ignored and \[\log Z=|r-s|.\]
Substituting this expression for \(\log Z\) into the preceding lower and upper bounds gives \[\begin{align} &\max\left\{|r-s|,~ r+s+\log(1-\cos\theta) \right\} - \log4 \\ &\le d_H(u,c) \\ &\le \max\left\{|r-s|,~r+s+\log(1-\cos\theta) \right\} + \log3. \end{align}\] ◻
Consequently, for \(u=(r,\xi)\) and \(c=(s,\zeta)\), we have \[\label{eq:radial-transverse-profile} d_H(u,c) = \max\left\{|r-s|,~r+s+\Lambda_\zeta(\xi) \right\}+O(1).\tag{3}\]
The additive constants in Lemma 7 are absolute constants. In particular, they do not depend on \(R_G\), \(u\), or \(c\). Thus the distance from \(u\) to \(c\), up to an absolute additive error, is governed by two expressions: \[|r-s|\qquad \text{and}\qquad r+s+\Lambda_\zeta(\xi).\] The first expression is the radial contribution. It is relevant when \(u\) lies close to the geodesic ray from \(a\) through \(c\), in which case the distance is essentially determined by the difference between the two radial coordinates. The second expression is the transverse contribution. It is relevant when the direction of \(u\) is separated from the direction of \(c\), in which case the distance is essentially determined by the sum of the two radial coordinates together with the logarithmic angular correction.
Except in the bounded transition range where these two expressions are comparable, one of them determines the distance up to an absolute additive error. The transition range will be used only in the analysis; it does not need to be stored explicitly in the signature, because the rounded radial expression already gives the required one-sided lower estimate there.
We now use this decomposition to describe how a center \(c\) affects the fixed bucket \(B\). For a center \(c\in B_H(a,3R_G)\), define its one-center distance profile on \(B\) by \[f_c: B \longrightarrow \mathbb{R},\qquad f_c(u)=d_H(u,c).\] The construction does not choose a finite net of possible centers \(c\). Instead, for each bucket \(B\), it records the distance functions that these centers induce on \(B\). Thus two centers are treated in the same way on \(B\) if their functions \(f_c\) agree on \(B\) up to the additive error allowed in the construction.
By Lemma 7, such a distance function is described, within the required additive error, by the radial coordinate \(s=d_H(a,c)\) and by the angular term \(\Lambda_\zeta(\xi)\) on the angular cap \(U_B\). The radial–transverse transition range is handled in the analysis and does not require a separate signature label. We therefore keep only a rounded radial coordinate, a finite angular record on \(U_B\), and a rounded level parameter. The radial–transverse transition range is handled only in the analysis and is not stored as part of the signature.
This finite record is called a one-center distance signature. A signature is neither a coreset point nor an artificial center. It is only an index describing one possible rounded distance function on the fixed bucket \(B\). For each signature \(\gamma\), let \[F_\gamma: B \longrightarrow \mathbb{R}\] denote the corresponding approximate distance profile, which we call the score function of \(\gamma\). Finally, put \[\tau=\Delta+1=\alpha\varepsilon R_G+1.\] This is the additive scale used for rounding the radial and level parameters.
Lemma 8. Let \(B\) be a shell–cone bucket around an anchor \(a\). Then there exists a finite family \(\mathcal{F}(B)\) of one-center distance signatures such that \[|\mathcal{F}(B)| = O\left(\left(\frac{1}{\varepsilon}\right)^{D+1}\right).\] Moreover, for every center \[c\in B_H(a,3R_G)\] and every level \[0\le \lambda\le 4R_G+1,\] there exists a signature \[\gamma(c,\lambda) \in \mathcal{F}(B)\] whose score function \(F_{\gamma(c,\lambda)}: B \to \mathbb{R}\) satisfies:
for every \(u\in B\), \[F_{\gamma(c,\lambda)}(u) \le d_H(u,c)+\eta_1\]
for every \(u\in B\) satisfying \(d_H(u,c) \ge \lambda\), \[F_{\gamma(c,\lambda)}(u) \ge d_H(u,c)-\eta_1.\]
Here \[\eta_1=C_{\eta}(\alpha\varepsilon R_G+1).\]
Proof. Apply the isometry sending \(a\) to the origin. We write \[u=(r,\xi)\in B, \qquad c=(s,\zeta), \qquad 0\le s\le 3R_G.\] The bucket \(B\) has radial width at most \[\Delta=\alpha\varepsilon R_G\] and angular diameter at most \(\alpha \varepsilon\). Put \[\tau=\Delta+1=\alpha \varepsilon R_G+1.\] Since \(\tau \ge 1\), all absolute additive constants arising from Lemma 7 can be absorbed into \(C \tau\).
For \(u=(r,\xi) \in B\), define \[R_s(u)=|r-s|\] and \[T_{s,\zeta}(u)=r+s+\Lambda_\zeta(\xi).\] It will be useful to write the angular term in the equivalent form \[h_\zeta(\xi) := -\Lambda_\zeta(\xi) = -\log\bigl(1-\cos\angle(\xi,\zeta)\bigr).\] Thus \[T_{s,\zeta}(u) = r+s-h_\zeta(\xi).\] Also put \[M_{s,\zeta}(u) = \max\{R_s(u),T_{s,\zeta}(u)\}.\] By Lemma 7, \[M_{s,\zeta}(u)-\log4 \le d_H(u,c) \le M_{s,\zeta}(u)+\log3.\] Thus it is enough to approximate \(M_{s,\zeta}\) on \(B\) up to additive error \(C \tau\).
We construct a signature by recording three finite pieces of information: a rounded radial value, a rounded level value, and an angular record on \(U_B\). The radial–transverse transition regions are used only in the analysis. They are not stored as part of the signature.
Step 1: Rounded radial coordinate. Partition the interval \([0,3R_G]\) into intervals of length \(\tau\). Let \(\widehat s\) be a representative of the interval containing \(s\). Then \[|s-\widehat s| \le \tau.\] Therefore, for every \(u\in B\), \[\bigl||r-s|-|r-\widehat s|\bigr| \le |s-\widehat s| \le \tau\] and \[|(r+s)-(r+\widehat s)| \le \tau.\] The number of possible rounded radial values is \[O\left(1+\frac{R_G}{\tau}\right) = O\left(\frac{1}{\varepsilon}\right),\] because \(\tau=\alpha \varepsilon R_G+1.\)
Step 2: Rounded level. Partition the interval \([0,4R_G+1]\) into intervals of length \(\tau\). Let \(\widehat \lambda\) be a representative of the interval containing \(\lambda\). Then \[|\lambda-\widehat\lambda|\le\tau.\] The number of possible rounded levels is again \[O\left(1+\frac{R_G}{\tau}\right) = O\left(\frac{1}{\varepsilon}\right).\] The rounded level is not needed for the upper estimate. It is used only for the lower estimate on the set of points satisfying \(d_H(u,c)\ge\lambda\).
Step 3: Angular records on \(U_B\). We now define the angular records. Near a singular direction, a uniform angular grid is not the right object to use. Instead, we use cells whose shape follows the relevant distance scale. In the present setting, this scale is the logarithmic angular depth \[h_\zeta(\xi) = -\log\bigl(1-\cos\angle(\xi,\zeta)\bigr).\] We use angular records of total size \[O\left(\left(\frac{1}{\varepsilon}\right)^{D-1}\right).\] There are two cases.
Transverse-safe case. Suppose first that the angular distance from \(\zeta\) to \(U_B\) is at least a sufficiently large constant multiple of \(\alpha \varepsilon\). Then the logarithmic angular term has no singularity on \(U_B\). More precisely, for every \(\xi\in U_B\), \[\angle(\xi,\zeta)\ge c\alpha\varepsilon\] for a fixed constant \(c>0\).
On this region both \(\Lambda_\zeta\) and \(h_\zeta=-\Lambda_\zeta\) have Lipschitz constant \(O(1/\alpha\varepsilon)\). Indeed, if \(\phi=\angle(\xi,\zeta)\), then \[\frac{d}{d\phi}h_\zeta(\phi) = -\frac{d}{d\phi}\log(1-\cos\phi) = -\frac{\sin\phi}{1-\cos\phi} = -\cot(\phi/2),\] and hence \[\left| \frac{d}{d\phi}h_\zeta(\phi) \right| = |\cot(\phi/2)| = O(1/\alpha\varepsilon)\] whenever \(\phi\ge c\alpha\varepsilon\). The same bound holds for \(\Lambda_\zeta\).
Hence, if \(\widehat\zeta\) is chosen from a spherical \(C\alpha\varepsilon\)-net, with \(C>0\) sufficiently small, then \[\left|\Lambda_\zeta(\xi)-\Lambda_{\widehat\zeta}(\xi) \right| \le C \le C \tau\] for all \(\xi \in U_B\). Combining this with \(|s-\widehat s|\le\tau\), we obtain \[\left| T_{s,\zeta}(u)-T_{\widehat s,\widehat\zeta}(u) \right| \le C\tau \qquad \text{for all }u\in B.\]
Near-ray case and truncated trapezoid angular records. It remains to consider the case where \(\zeta\) lies within angular distance \(O(\alpha\varepsilon)\) of \(U_B\). In this case \(\Lambda_\zeta\) may vary rapidly near the direction \(\zeta\), and an ordinary angular net does not give a uniform approximation on all of \(U_B\). We therefore use a truncated trapezoid record in the \((r,h_\zeta)\)-coordinates.
Let \[r^-_B\le r\le r^+_B\] be the radial interval of \(B\). Since \(B\) has radial width at most \(\Delta\), we have \[r^+_B-r^-_B\le\Delta\le\tau.\] Moreover, by the construction of the shell–cone buckets in the large-scale regime, \[r^+_B=O(R_G).\] For the rounded data \((\widehat s,\widehat\lambda)\), define the truncation depth \[H_B(\widehat s,\widehat\lambda):=r^+_B+\widehat s-\widehat\lambda+C_0\tau,\] where \(C_0>0\) is a sufficiently large absolute constant. Since \[r^+_B=O(R_G),\qquad \widehat s\le 3R_G+\tau,\qquad \widehat\lambda\ge0,\] we have \[H_B(\widehat s,\widehat\lambda)=O(R_G+\tau).\] Together with \[\tau\ge \alpha\varepsilon R_G,\] this implies \[\left\lceil \frac{H_B(\widehat s,\widehat\lambda)}{\tau} \right\rceil = O\left(\frac{1}{\varepsilon}\right).\]
Define \[A_0(\zeta) = \{\xi\in U_B:h_\zeta(\xi)<\tau\},\] and, for \(j=1,\ldots,J\), \[A_j(\zeta) = \{\xi\in U_B:j\tau\le h_\zeta(\xi)<(j+1)\tau\}.\] Thus the first strip absorbs the bounded range \(h_\zeta(\xi)<0\), whose contribution is within an absolute additive constant and hence within \(C\tau\). In the angular picture, the strips \(A_j(\zeta)\) are annular trapezoid-like regions around the ray \(\zeta\). Their angular widths decrease exponentially as \(j\) increases. The last strip is truncated at depth \(H_B(\widehat s,\widehat\lambda).\)
A truncated trapezoid angular record consists of the depth-strip rule up to the truncation depth \(H_B(\widehat s,\widehat\lambda)\), together with the tangential cell information needed to locate the corresponding strip inside the fixed cap \(U_B\). In the near-ray case, the logarithmic depth coordinate contributes \[O\left(\frac{1}{\varepsilon}\right)\] levels. At each depth level, the remaining tangential cross-section has dimension at most \(D-2\), and hence can be discretized using \[O\left(\left(\frac{1}{\varepsilon}\right)^{D-2}\right)\] cells. The tangential cell information is chosen in local coordinates centered at the near-ray direction. Thus the pair consisting of the depth level and the tangential cell also fixes the rounded near-ray direction type relevant to the strip. Hence no additional \((D-1)\)-dimensional discretization of \(\zeta\) is counted separately. Consequently, the total number of near-ray angular records is \[O\left(\frac{1}{\varepsilon}\right) \cdot O\left(\left(\frac{1}{\varepsilon}\right)^{D-2}\right) = O\left(\left(\frac{1}{\varepsilon}\right)^{D-1}\right).\] Thus the near-ray angular records satisfy the same angular-record budget as the transverse-safe records.
The associated angular record assigns each direction \(\xi \in U_B\) to one of two types. Either \(\xi\) belongs to one of the truncated depth strips, in which case the record provides a rounded angular-depth value \[\widetilde{h}_\gamma(\xi)\in \mathbb{R},\] or \(\xi\) belongs to the deep tail, in which case no angular-depth value is used. Thus the record itself determines whether the transverse score is evaluated at \(\xi\); this decision does not require access to the original direction \(\zeta\). More precisely, if \(\xi\) is assigned to the depth strip \(A_j\), then we set \[\widetilde{h}_\gamma(\xi)=j\tau.\] If \(\xi\) is assigned to the deep tail, then the transverse expression is ignored and only the rounded radial expression is used.
Let us record the approximation property on the truncated part. If \(\xi\in A_j(\zeta)\) and \(h_\zeta(\xi)\le H_B(\widehat s,\widehat\lambda),\) then by definition \[j\tau \le h_\zeta(\xi) < (j+1)\tau\] and \[\widetilde{h}_\gamma(\xi)=j\tau.\] For \(j\ge1\), we have \[0\le h_\zeta(\xi)-\widetilde{h}_\gamma(\xi)<\tau.\] For \(j=0\), the value \(h_\zeta(\xi)\) lies in the interval \([-\log 2,\tau)\). Hence, after increasing the absolute constant, \[|h_\zeta(\xi)-\widetilde{h}_\gamma(\xi)| \le C\tau\] on all truncated strips. Hence, on the truncated part, \[\left| h_\zeta(\xi)-\widetilde{h}_\gamma(\xi) \right| \le C\tau.\] Consequently, for \[\widetilde{T}_\gamma(u) := r+\widehat s-\widetilde{h}_\gamma(\xi),\] we have, whenever \(h_\zeta(\xi)\le H_B(\widehat{s},\widehat{\lambda})\), \[\widetilde{T}_\gamma(u)-T_{s,\zeta}(u) = (\widehat s-s) + \bigl(h_\zeta(\xi)-\widetilde{h}_\gamma(\xi)\bigr).\] Since \[|\widehat s-s|\le\tau\] and \[\left| h_\zeta(\xi)-\widetilde{h}_\gamma(\xi) \right| \le C\tau,\] we obtain \[\left| \widetilde{T}_\gamma(u)-T_{s,\zeta}(u) \right| \le C\tau\] on the truncated part.
We now justify that the truncation loses no point on which the lower estimate is needed, unless that point is already handled by the radial term. Fix a sufficiently large absolute constant \(K\ge1\), and decompose \(B\) into \[\mathcal{R}_K = \{u\in B:T_{s,\zeta}(u)<R_s(u)-K\tau\},\] \[\mathcal{X}_K = \{u\in B:|T_{s,\zeta}(u)-R_s(u)|\le K\tau\},\] and \[\mathcal{T}_K = \{u\in B:T_{s,\zeta}(u)>R_s(u)+K\tau\}.\] Here \(\mathcal{R}_K\) is the radial-dominant region, \(\mathcal{T}_K\) is the transverse-dominant region, and \(\mathcal{X}_K\) is the transition region. This decomposition is used only in the proof.
Suppose that \[u\in B\setminus\mathcal{R}_K \qquad\text{and}\qquad d_H(u,c)\ge\lambda.\] By Lemma 7, \[d_H(u,c)\le M_{s,\zeta}(u)+\log3.\] Hence \[M_{s,\zeta}(u)\ge \lambda-\log3.\] Since \(u\notin\mathcal{R}_K\), we have \[T_{s,\zeta}(u)\ge R_s(u)-K\tau,\] or equivalently \[R_s(u)\le T_{s,\zeta}(u)+K\tau.\] Therefore \[M_{s,\zeta}(u) = \max\{R_s(u),T_{s,\zeta}(u)\} \le T_{s,\zeta}(u)+K\tau.\] Combining the last two inequalities gives \[T_{s,\zeta}(u) \ge \lambda-\log3-K\tau.\] Since \[T_{s,\zeta}(u)=r+s-h_\zeta(\xi),\] we obtain \[h_\zeta(\xi) \le r+s-\lambda+\log3+K\tau.\] Using \[r\le r^+_B, \qquad |s-\widehat s|\le\tau, \qquad |\lambda-\widehat\lambda|\le\tau,\] we obtain \[h_\zeta(\xi) \le r^+_B+\widehat s-\widehat\lambda+(K+2+\log3)\tau \le H_B(\widehat s,\widehat\lambda),\] by choosing \(C_0 \ge K+2+\log3\). Therefore every point \(u\in B\setminus\mathcal{R}_K\) with \(d_H(u,c)\ge\lambda\) lies inside the truncated part of the trapezoid decomposition. Equivalently, points beyond the truncation depth are irrelevant for the one-sided lower estimate unless they are radial-dominant. In that case they are handled by the rounded radial term.
On the transition region \(\mathcal{X}_K\), no further angular approximation is needed. Indeed, if \(u\in\mathcal{X}_K\), then \[|T_{s,\zeta}(u)-R_s(u)|\le K\tau.\] Thus \[M_{s,\zeta}(u) = \max\{R_s(u),T_{s,\zeta}(u)\} \le R_s(u)+K\tau.\] Since the rounded radial term \[\widetilde{R}_\gamma(u):=|r-\widehat s|\] satisfies \[\widetilde{R}_\gamma(u) \ge R_s(u)-\tau,\] we have \[M_{s,\zeta}(u) \le \widetilde{R}_\gamma(u)+(K+1)\tau.\] Using \[d_H(u,c)\le M_{s,\zeta}(u)+\log3,\] we obtain \[d_H(u,c) \le \widetilde{R}_\gamma(u)+(K+1)\tau+\log3.\] Since \(\tau \ge 1\), we have \(\log 3 \le (\log 3)\tau\). By choosing the absolute constant \(C_1 \ge K + 1 + \log 3\), we obtain\[\widetilde{R}_\gamma(u) \ge d_H(u,c)-C_1\tau\] on the transition region.
Thus the transition region is automatically protected by the score function: no explicit transition label is needed in the signature, because the score function is always at least \(\widetilde{R}_\gamma(u).\) Consequently, in both the transverse-safe case and the near-ray case, the angular behaviour of \(c\) on \(B\) is represented by one of \[O\left(\left(\frac{1}{\varepsilon}\right)^{D-1}\right)\] angular records.
Step 4: Defining the score function and proving the two inequalities. A one-center distance signature \(\gamma\) consists of:
a rounded radial value \(\widehat{s}\),
a rounded level value \(\widehat{\lambda}\),
an angular record on \(U_B\), using either the transverse-safe angular net or the truncated trapezoid record in the near-ray case.
For such a signature, define \[\widetilde{R}_\gamma(u) = |r-\widehat s|.\] In the transverse-safe case, define the rounded transverse expression by \[\widetilde{T}_\gamma(u) = r+\widehat{s}+\Lambda_{\widehat\zeta}(\xi),\] where \(\widehat{\zeta}\) is the representative direction of \(\zeta\). In the near-ray case, the score function is defined using only the finite angular record. If the record assigns \(\xi\) to a truncated depth strip, define \[\widetilde{T}_\gamma(u) = r+\widehat s-\widetilde{h}_\gamma(\xi),\] and set \[F_\gamma(u) = \max\{\widetilde{R}_\gamma(u),\widetilde{T}_\gamma(u)\}.\] If the record assigns \(\xi\) to the deep tail, then no transverse value is used, and we define \[F_\gamma(u)=\widetilde{R}_\gamma(u).\] Equivalently, \[F_\gamma(u) = \begin{cases} \max\{\widetilde{R}_\gamma(u),\widetilde{T}_\gamma(u)\}, & \text{if \(\xi\) is assigned to a truncated depth strip},\\[1mm] \widetilde{R}_\gamma(u), & \text{if \(\xi\) is assigned to the deep tail}. \end{cases}\] In the transverse-safe case, we define \[F_\gamma(u) = \max\{\widetilde{R}_\gamma(u),\widetilde{T}_\gamma(u)\}.\]
Notice that the evaluation of \(F_\gamma(u)\) relies only on the rounded radial expression, the rounded angular record, and the truncation depth. The transition region \(\mathcal{X}_K\) is used only in the proof and does not require an explicit transition label in the signature.
We first prove the upper estimate. Let \(C_{\mathrm{ts}}\) be the absolute constant in the transverse-safe angular approximation, and let \(C_{\mathrm{nr}}\) be the absolute constant in the near-ray depth-strip approximation. Choose \[C_{\mathrm{upper}} \ge \max\{1,C_{\mathrm{ts}},C_{\mathrm{nr}}\}.\] In the transverse-safe case, the bounds from Step 1 and the Lipschitz estimate for the angular term give \[|\widetilde{R}_\gamma(u)-R_s(u)| \le \tau\] and \[|\widetilde{T}_\gamma(u)-T_{s,\zeta}(u)|\le C_{\mathrm{ts}}\tau.\] Hence \[F_\gamma(u) \le M_{s,\zeta}(u)+\max\{1,C_{\mathrm{ts}}\} \tau.\] In the near-ray case, if \(u\) lies in the truncated part, then the depth-strip estimate gives \[|\widetilde{T}_\gamma(u)-T_{s,\zeta}(u)|\le C_{\mathrm{nr}} \tau,\] and again \[F_\gamma(u) \le M_{s,\zeta}(u)+\max\{1,C_{\mathrm{nr}}\}\tau.\] If \(u\) lies beyond the truncation depth, then by definition \[F_\gamma(u)=\widetilde{R}_\gamma(u).\] Since \[\widetilde{R}_\gamma(u) \le R_s(u)+\tau \le M_{s,\zeta}(u)+\tau,\] we have \[F_\gamma(u) \le M_{s,\zeta}(u)+C_{\mathrm{upper}} \tau.\] Using \[d_H(u,c)\ge M_{s,\zeta}(u)-\log4,\] we obtain \[F_\gamma(u) \le d_H(u,c)+(C_{\mathrm{upper}}+\log 4) \tau.\]
We now prove the lower estimate on the set \[\{u\in B:d_H(u,c) \ge \lambda \}.\] Let \(u\in B\) satisfy \(d_H(u,c) \ge \lambda.\) Choose \[C_{\mathrm{lower}} \ge \max\{1,K+1,C_{\mathrm{nr}}\}.\] If \(u \in \mathcal{R}_K\), then \[T_{s,\zeta}(u)<R_s(u)-K\tau,\] so \[M_{s,\zeta}(u)=R_s(u).\] Since \[\widetilde{R}_\gamma(u)\ge R_s(u)-\tau,\] and since \(F_\gamma(u) \ge \widetilde{R}_\gamma(u)\), we get \[F_\gamma(u) \ge M_{s,\zeta}(u)-\tau.\] If \(u \in \mathcal{X}_K\), then, as shown above, \[M_{s,\zeta}(u) \le \widetilde{R}_\gamma(u)+(K+1)\tau.\] Thus \[F_\gamma(u) \ge \widetilde{R}_\gamma(u) \ge M_{s,\zeta}(u)-(K+1)\tau.\] If \(u \in \mathcal{T}_K\), then \(T_{s,\zeta}(u)>R_s(u)+K\tau\), and hence \[M_{s,\zeta}(u)=T_{s,\zeta}(u).\] Moreover, since \(u \notin \mathcal{R}_K\) and \(d_H(u,c) \ge \lambda\), the truncation argument from Step 3 gives \[h_\zeta(\xi)\le H_B(\widehat{s},\widehat{\lambda}).\] Therefore \(u\) lies in the truncated part, and the depth-strip estimate applies: \[\widetilde{T}_\gamma(u) \ge T_{s,\zeta}(u)-C_{\mathrm{nr}}\tau.\] Since \[F_\gamma(u)\ge \widetilde{T}_\gamma(u),\] we get \[F_\gamma(u) \ge M_{s,\zeta}(u)-C_{\mathrm{nr}}\tau.\] Combining the three cases, for every \(u\in B\) satisfying \(d_H(u,c) \ge \lambda\), we have \[F_\gamma(u) \ge M_{s,\zeta}(u)-C_{\mathrm{lower}}\tau.\] Using \[d_H(u,c)\le M_{s,\zeta}(u)+\log3,\] we obtain \[F_\gamma(u) \ge d_H(u,c)-(C_{\mathrm{lower}}+\log 3)\tau.\]
Indeed, in the transverse-safe case this is the usual spherical-net bound on the \((D-1)\)-dimensional angular space. In the near-ray case, the truncated trapezoid record can also be encoded with \[O\left(\left(\frac{1}{\varepsilon}\right)^{D-1}\right)\] possibilities: the logarithmic depth contributes one discrete coordinate, and the remaining tangential cross-section has dimension \(D-2\). Therefore \[|\mathcal{F}(B)| = O\left(\frac{1}{\varepsilon}\right) \cdot O\left(\frac{1}{\varepsilon}\right) \cdot O\left(\left(\frac{1}{\varepsilon}\right)^{D-1}\right) = O\left(\left(\frac{1}{\varepsilon}\right)^{D+1}\right).\] Finally, choose \[C_\eta \ge \max\{ C_0,~C_{\mathrm{upper}}+\log4,~C_{\mathrm{lower}}+\log3 \}.\] Since \(\tau=\alpha\varepsilon R_G+1,\) set \[\eta_1 = C_\eta\tau = C_\eta(\alpha\varepsilon R_G+1).\] Then the upper estimate proved above gives \[F_\gamma(u) \le d_H(u,c)+\eta_1\] for every \(u\in B\), and the lower estimate gives \[F_\gamma(u) \ge d_H(u,c)-\eta_1\] for every \(u\in B\) satisfying \(d_H(u,c) \ge \lambda\). This completes the proof. ◻
Remark 5. The near-ray case is the only delicate part of Lemma 8. In this case, the angular term \(\Lambda_\zeta\) has a singularity at the direction \(\zeta\), and therefore it cannot be uniformly approximated on \(U_B\) by an ordinary angular net. The proof avoids this difficulty by using the logarithmic angular-depth coordinate \[h_\zeta(\xi) = -\log\bigl(1-\cos\angle(\xi,\zeta)\bigr)\] and by truncating the resulting depth decomposition at the scale \[H_B(\widehat{s},\widehat{\lambda}) = r_B^+ + \widehat{s}-\widehat{\lambda}+C_0\tau.\] The role of the truncation is only to support the one-sided lower estimate. Points beyond the truncation depth do not need a transverse approximation unless they are relevant to the lower estimate; the proof shows that any point \(u\in B\setminus\mathcal{R}_K\) with \(d_H(u,c) \ge \lambda\) must satisfy \[h_\zeta(\xi) \le r_B^+ + \widehat{s}-\widehat{\lambda}+O(\tau) \le H_B(\widehat{s},\widehat{\lambda}).\] The bounded transition region also requires no separate signature label. Indeed, on the transition region the two expressions \(R_s(u)\) and \(T_{s,\zeta}(u)\) differ by only \(O(\tau)\), and the score function always satisfies \[F_\gamma(u)\ge \widetilde{R}_\gamma(u).\] The rounded radial term therefore gives the required lower estimate there. Consequently, the signature only needs to store the rounded radial value, the rounded level value, and the angular record.
For a bucket \(B\), define \[\mathcal{G}(B) = \mathcal{F}(B)^k.\] An element \[\Gamma=(\gamma_1,\ldots,\gamma_k)\in\mathcal{G}(B)\] is called a coarse \(k\)-center distance signature. Define \[F_\Gamma(u) = \min_{h=1,\ldots,k}F_{\gamma_h}(u).\]
We first record the elementary stability of lower envelopes.
Lemma 9. Let \(f_h,g_h:X \to \mathbb{R}\), \(h=1,\ldots,k\), satisfy \[|f_h(x)-g_h(x)| \le \eta\] for all \(x \in X\) and all \(h\). Then \[\left| \min_h f_h(x) - \min_h g_h(x) \right| \le \eta\] for every \(x \in X\).
Proof. For every \(h\), \[f_h(x)\le g_h(x)+\eta.\] Taking the minimum over \(h\) gives \[\min_h f_h(x) \le \min_h g_h(x)+\eta.\] Interchanging \(f_h\) and \(g_h\) gives the reverse inequality. ◻
For the robust one-sided signatures, we use the following bucket-level argument.
Lemma 10. Let \(B\) be a nonempty shell–cone bucket around an anchor \(a_i\). Let \(C\subset \mathbb{H}^D\), with \(|C|\le k\), cover the anchors at scale \(R_G\). Then there exists \[\Gamma(C,B) \in \mathcal{G}(B)\] such that, if \[q_{B,\Gamma} \in \mathop{\mathrm{arg\,max}}_{q\in B}F_\Gamma(q),\] then for every \(p \in B\), \[d_H(p,C) \le d_H(q_{B,\Gamma},C)+2\eta_1.\]
Proof. Let \[\lambda_B(C) = \max_{u\in B}d_H(u,C),\] and choose \[p^* \in \mathop{\mathrm{arg\,max}}_{u\in B}d_H(u,C).\] Thus \[d_H(p^*,C)=\lambda_B(C).\]
First note that the level \(\lambda_B(C)\) is in the range required by Lemma 8. Indeed, since \(B \subseteq P_i\), every \(u \in B\) satisfies \[d_H(u,a_i)\le R_G.\] Moreover, since \(C\) covers the anchors at scale \(R_G\), \[d_H(a_i,C) \le R_G.\] Therefore, for every \(u \in B\), \[d_H(u,C) \le d_H(u,a_i)+d_H(a_i,C) \le 2R_G.\] Hence \[0\le \lambda_B(C)\le 2R_G\le 4R_G+1.\]
Let \(C_B \subseteq C\) be the set of centers that are nearest to at least one point of \(B\), \[C_B = \{c\in C:\text{ there exists }u\in B \text{ such that }d_H(u,c)=d_H(u,C)\}.\] The set \(C_B\) is nonempty because \(B\) is nonempty. Moreover, for every \(u \in B\), \[d_H(u,C) = \min_{c\in C_B}d_H(u,c).\] By Lemma 5, every center in \(C_B\) lies in \(B_H(a_i,3R_G)\). Write \[C_B=\{b_1,\ldots,b_m\}, \qquad 1\le m\le k.\]
For each \(\ell=1,\ldots,m\), apply Lemma 8 to the center \(b_\ell\) with the common level \(\lambda_B(C)\), and choose \[\gamma_\ell = \gamma(b_\ell,\lambda_B(C)) \in \mathcal{F}(B).\] If \(m<k\), pad the tuple by repeating \(\gamma_m\). Thus we obtain an element \[\Gamma(C,B) = (\gamma_1,\ldots,\gamma_m,\gamma_m,\ldots,\gamma_m) \in \mathcal{G}(B).\] For this tuple, \[F_\Gamma(u) = \min_{\ell=1,\ldots,m}F_{\gamma_\ell}(u)\] for every \(u \in B\). Since \[d_H(p^*, C) = \min_{c\in C_B}d_H(p^*,c) = \lambda_B(C),\] we have \[d_H(p^*, b_\ell)\ge \lambda_B(C)\] for every \(\ell=1,\ldots,m\). Lemma 8 gives \[F_{\gamma_\ell}(p^*) \ge d_H(p^*,b_\ell)-\eta_1\] for every \(\ell\). Taking the minimum over \(\ell\), we obtain \[\begin{align} F_\Gamma(p^*) = \min_{\ell=1,\ldots,m}F_{\gamma_\ell}(p^*) \ge \min_{\ell=1,\ldots,m}d_H(p^*,b_\ell)-\eta_1 = d_H(p^*,C)-\eta_1 = \lambda_B(C)-\eta_1. \end{align}\]
By the maximality of \(q_{B,\Gamma}\), \[F_\Gamma(q_{B,\Gamma}) \ge F_\Gamma(p^*) \ge \lambda_B(C)-\eta_1.\] On the other hand, Lemma 8 gives, for every \(\ell=1,\ldots,m\), \[F_{\gamma_\ell}(q_{B,\Gamma}) \le d_H(q_{B,\Gamma},b_\ell)+\eta_1.\] Taking the minimum over \(\ell\), and using \[d_H(q_{B,\Gamma},C) = \min_{\ell=1,\ldots,m}d_H(q_{B,\Gamma},b_\ell),\] we get \[F_\Gamma(q_{B,\Gamma}) \le d_H(q_{B,\Gamma},C)+\eta_1.\] Combining the last two inequalities gives \[\lambda_B(C) \le d_H(q_{B,\Gamma},C)+2\eta_1.\]
Finally, every \(p\in B\) satisfies \[d_H(p,C) \le \lambda_B(C).\] Therefore \[d_H(p,C) \le d_H(q_{B,\Gamma},C)+2\eta_1,\] as claimed. ◻
We now turn the structural results into a coreset. For every nonempty shell–cone bucket \(B\) and every \(\Gamma\in\mathcal{G}(B),\) choose \[q_{B,\Gamma} \in \operatorname*{argmax}_{q\in B}F_\Gamma(q).\] Define \[P_\varepsilon = A_k \cup \left\{ q_{B,\Gamma}: B\text{ is nonempty},~\Gamma\in\mathcal{G}(B) \right\}.\]
Recall that, by Lemma 8, \[\eta_1 = C_\eta(\alpha\varepsilon R_G+1).\] Choose \(\alpha>0\) sufficiently small so that \[8C_\eta \alpha \le \frac{1}{2}.\] Define the large-scale threshold by \[R_{1} = \frac{16C_\eta}{\varepsilon}.\] The present large-scale construction is used only in the regime \(R_G\ge R_{1}.\) The remaining range \(R_0 \le R_G \le R_1\) is handled by the intermediate-scale construction.
Theorem 6. Assume that \(R_G \ge R_1,\) and construct \(P_\varepsilon \subseteq P\) by the large-scale shell–cone construction above. Let \[C_{P_\varepsilon} \in \operatorname*{argmin}_{\substack{C\subseteq\mathbb{H}^{D}\\ |C|\le k}} \Phi_{P_\varepsilon}(C)\] be an optimal continuous \(k\)-center solution for \(P_\varepsilon\). Then \[\Phi_P(C_{P_\varepsilon}) \le (1+\varepsilon)\mathrm{OPT}_k (P).\]
Proof. We first prove the large-scale analogue of the transfer inequality. Let \(C \subseteq \mathbb{H}^{D}\) with \(|C|\le k\) be any center set that covers the anchors at scale \(R_G\), that is, \[\Phi_{A_k}(C)\le R_G.\] Choose \[p^* \in \operatorname*{argmax}_{p\in P} d_H(p,C).\] If \(p^* \in A_k\), then \(p^* \in P_\varepsilon\), and hence \[\Phi_P (C) = d_H(p^*,C) \le \Phi_{P_\varepsilon}(C).\] Assume therefore that \(p^* \notin A_k\), and let \(B\) be the shell–cone bucket containing \(p^*\). By Lemma 10, there exists \[\Gamma(C,B)\in\mathcal{G}(B)\] such that \[d_H(p^*,C) \le d_H(q_{B,\Gamma},C)+2\eta_1.\] Since \(q_{B,\Gamma}\in P_\varepsilon\), we have \[d_H(q_{B,\Gamma},C) \le \Phi_{P_\varepsilon}(C).\] Thus, for every center set \(C\) covering the anchors at scale \(R_G\), we have \[\label{eq:large-transfer} \Phi_P (C) \le \Phi_{P_\varepsilon}(C)+2\eta_1.\tag{4}\]
We now apply this inequality to \(C_{P_\varepsilon}\). Since \[A_k\subseteq P_\varepsilon,\] the anchor set \(A_k\) is a feasible center set for the reduced instance. Moreover, \[\Phi_{P_\varepsilon}(A_k) \le \Phi_P(A_k) = R_G.\] By the optimality of \(C_{P_\varepsilon}\) on \(P_\varepsilon\), \[\Phi_{P_\varepsilon}(C_{P_\varepsilon}) \le \Phi_{P_\varepsilon}(A_k) \le R_G.\] Since \(A_k \subseteq P_\varepsilon\), it follows that \[\Phi_{A_k}(C_{P_\varepsilon}) \le \Phi_{P_\varepsilon}(C_{P_\varepsilon}) \le R_G.\] Therefore \(C_{P_\varepsilon}\) covers the anchors at scale \(R_G\), and we may apply inequality 4 with \(C=C_{P_\varepsilon}\). This gives \[\Phi_P(C_{P_\varepsilon}) \le \Phi_{P_\varepsilon}(C_{P_\varepsilon}) + 2\eta_1.\]
Let \(C^*\) be an optimal continuous \(k\)-center solution for \(P\). Since \(P_\varepsilon \subseteq P\), we have \[\Phi_{P_\varepsilon}(C^*) \le \Phi_P(C^*) = \mathrm{OPT}_k (P).\] By the optimality of \(C_{P_\varepsilon}\) on \(P_\varepsilon\), \[\Phi_{P_\varepsilon}(C_{P_\varepsilon}) \le \Phi_{P_\varepsilon}(C^*) \le \mathrm{OPT}_k (P).\] Consequently, \[\Phi_P(C_{P_\varepsilon}) \le \mathrm{OPT}_k(P)+2\eta_1.\]
It remains to bound the additive error \(2\eta_1\). By the definition of \(\eta_1\), \[2\eta_1 = 2C_\eta(\alpha\varepsilon R_G+1).\] By Lemma 1, \[R_G \le 4\mathrm{OPT}_k (P).\] Hence \[2C_\eta \alpha \varepsilon R_G \le 8C_\eta \alpha \varepsilon \mathrm{OPT}_k (P) \le \frac{\varepsilon}{2}\mathrm{OPT}_k (P),\] where the last inequality follows from the choice of \(\alpha\).
It remains to control the additive constant \(2C_\eta\). Since \(R_G \ge R_1\) and Lemma 1 gives \(R_G \le 4\mathrm{OPT}_k (P)\), we have \[\mathrm{OPT}_k (P) \ge \frac{R_G}{4} \ge \frac{R_1}{4} = \frac{4C_\eta}{\varepsilon}.\] Therefore, \[2C_\eta \le \frac{\varepsilon}{2}\mathrm{OPT}_k (P).\] Combining the two estimates gives \[2\eta_1 \le \varepsilon\mathrm{OPT}_k (P).\] Substituting this into \[\Phi_P (C_{P_\varepsilon}) \le \mathrm{OPT}_k (P)+2\eta_1\] yields \[\Phi_P (C_{P_\varepsilon}) \le (1+\varepsilon)\mathrm{OPT}_k (P).\] ◻
By Lemma 4, the number of nonempty shell–cone buckets is \[O\left( k \left(\frac{1}{\varepsilon}\right)^D \right).\] By Lemma 8, the number of one-center distance signatures for \(B\) satisfies \[|\mathcal{F}(B)| = O\left( \left(\frac{1}{\varepsilon}\right)^{D+1} \right).\] A coarse \(k\)-center distance signature is an element of \[\mathcal{G}(B)=\mathcal{F}(B)^k.\] Therefore, \[|\mathcal{G}(B)| = |\mathcal{F}(B)|^k = O\left( \left(\frac{1}{\varepsilon}\right)^{k(D+1)} \right).\]
The construction stores at most one input point \(q_{B,\Gamma}\) for each pair \((B,\Gamma)\), where \(B\) is a nonempty shell–cone bucket and \(\Gamma \in \mathcal{G}(B)\). It also stores the \(k\) anchors in \(A_k\). Consequently, \[|P_\varepsilon| \le k+O\left( k \left(\frac{1}{\varepsilon}\right)^D \right) \cdot O\left( \left(\frac{1}{\varepsilon}\right)^{k(D+1)} \right) = O\left( k \left(\frac{1}{\varepsilon}\right)^{D+k(D+1)} \right).\] We may also write \[|P_\varepsilon| = \left(\frac{1}{\varepsilon}\right)^{O(kD)}.\] Consequently, for fixed \(D\), \(k\), and \(\varepsilon\), the large-scale coreset has constant size independent of the number \(n\) of input points and independent of the scale \(R_G\).
The large-scale construction uses the same initial preprocessing as the bounded-scale construction. Namely, the farthest-first anchor set \(A_k\), the covering radius \(R_G\), and the nearest-anchor partition \[P=P_1\mathbin{\dot{\cup}}\cdots\mathbin{\dot{\cup}}P_k\] are computed in \(O(kn)\) time. We therefore only need to account for the additional work required by the shell–cone profile construction.
For fixed \(D\), after applying the isometry \(\mu_{a_i}\) sending the anchor \(a_i\) to the origin, the polar coordinates \[\bigl(r_i(p),\xi_i(p)\bigr)\] of a point \(p\in P_i\) can be computed in \(O(1)\) time. We choose the angular cover to be a fixed canonical spherical grid at mesh \(O(\alpha\varepsilon)\). For fixed \(D\), after constant-size preprocessing depending only on \(D\) and \(\varepsilon\), the angular cell containing a direction \(\xi_i(p)\) can be found in \(O(1)\) time. The radial shell index is obtained by a single arithmetic operation. Hence assigning all input points to their shell–cone buckets takes \(O(n)\) time after the nearest-anchor partition is known.
For each nonempty bucket \(B\), the signature-count lemma gives \[|\mathcal{G}(B)| = |\mathcal{F}(B)|^k = \left(\frac{1}{\varepsilon}\right)^{O(kD)}.\] During a single scan of the input, whenever a point \(p\in B\) is encountered, the algorithm evaluates \(F_\Gamma(p)\) for every \(\Gamma \in \mathcal{G}(B)\) and updates the current maximizer \(q_{B,\Gamma}\). Since \[F_\Gamma(p) = \min_{h=1,\ldots,k}F_{\gamma_h}(p),\] one evaluation of \(F_\Gamma(p)\) takes \(O(k)\) time. Therefore the work charged to one input point is \[O\left(k\left(\frac{1}{\varepsilon}\right)^{O(kD)}\right).\] Summing over all \(n\) input points, the total time for evaluating all bucket–signature scores and maintaining the maximizers is \[O\left(nk\left(\frac{1}{\varepsilon}\right)^{O(kD)}\right).\] The initialization of the maximizers for all nonempty bucket–signature pairs is bounded by the same expression, up to fixed-parameter factors, because the number of nonempty buckets is at most \(n\). Thus the total large-scale construction time is \[O(kn) + O(n) + O\left(nk\left(\frac{1}{\varepsilon}\right)^{O(kD)}\right) = O\left(nk\left(\frac{1}{\varepsilon}\right)^{O(kD)}\right).\] In particular, for fixed \(D\), \(k\), and \(\varepsilon\), the large-scale shell–cone coreset can be constructed in \(O(n)\) time.
Theorem 7 (Large-scale continuous \(k\)-center coreset). Let \(D\ge 1\), let \(0<\varepsilon<1\), and let \(P\subset \mathbb{B}^{D}\) be finite. Run Gonzalez’s farthest-first traversal for \(k\) steps, and let \[A_k=\{a_1,\ldots,a_k\},\qquad R_G=\Phi_P(A_k).\] Let \(C_\eta>0\) be the absolute constant in the large-scale profile error bound, and set \[R_1=\frac{16C_\eta}{\varepsilon}.\] Assume that \(R_G\ge R_1\). Construct \(P_\varepsilon\subseteq P\) by the large-scale profile construction as follows. If \(D\ge 2\), partition each nearest-anchor cluster into shell–cone buckets. If \(D=1\), use the same construction with only the radial shell decomposition, since there is no angular component. For every nonempty bucket \(B\) and every coarse \(k\)-center signature \[\Gamma\in \mathcal{G}(B)=\mathcal{F}(B)^k,\] retain one point \[q_{B,\Gamma}\in \arg\max_{q\in B} F_\Gamma(q).\] Together with the anchors, define \[P_\varepsilon = A_k\cup \{q_{B,\Gamma}: B \text{ is a nonempty bucket},~\Gamma\in\mathcal{G}(B)\}.\] Then every optimal continuous \(k\)-center solution \(C_{P_\varepsilon}\) for \(P_\varepsilon\) satisfies \[\Phi_P(C_{P_\varepsilon}) \le (1+\varepsilon)\mathrm{OPT}_k (P).\] Moreover, \[|P_\varepsilon| = O\left( k\left(\frac{1}{\varepsilon}\right)^{D+k(D+1)} \right) = O\left( k\left(\frac{1}{\varepsilon}\right)^{(k+1)D+k} \right),\] and the construction time is \[O\left( nk\left(\frac{1}{\varepsilon}\right)^{O(kD)} \right).\] Consequently, for fixed \(D\), \(k\), and \(\varepsilon\), the large-scale coreset can be constructed in \(O(n)\) time.
The large-scale shell–cone construction uses the coarse profile \[d_H(u,c) = \max\{|r-s|,\;r+s+\Lambda_\zeta(\xi)\}+O(1), \qquad \Lambda_\zeta(\xi)=\log(1-\cos\angle(\xi,\zeta)).\] While this coarse profile was sufficient to obtain the \((1+\varepsilon)\)-approximation when \(R_G \ge R_1\), it is not accurate enough for our analysis in the range \[R_0 \le R_G \le R_1.\] In this range we keep the same shell–cone representative scheme, but replace the coarse profile lemma by an exact-profile lemma based on the hyperbolic law of cosines.
Fix a sufficiently small absolute constant \(\beta>0\), to be chosen later, and put \[\delta=\beta\varepsilon R_G.\] We use the same farthest-first anchors \[A_k=\{a_1,\ldots,a_k\},\] the same nearest-anchor partition \[P=P_1\mathbin{\dot{\cup}}\cdots\mathbin{\dot{\cup}}P_k,\] and the same anchor-centered polar coordinates as in the large-scale construction. The intermediate bucket decomposition differs only in the mesh size: the radial intervals have length \(\delta,\) and the angular caps have diameter at most \(\beta\varepsilon.\) Thus, for each anchor \(a_i\), we partition \([0,R_G]\) into intervals \(I_j\) of length \(\delta\), cover \(S^{D-1}\) by sets \(U_\ell\) of angular diameter at most \(\beta\varepsilon\), and define \[B(i,j,\ell) = \{p\in P_i\setminus A_k: r_i(p)\in I_j,\;\xi_i(p)\in U_\ell\}.\] For \(D=1\), the angular cover is interpreted as the two-point sphere \(S^0\), and the construction reduces to the radial decomposition. Since \(\beta>0\) is fixed, the same counting argument as in Lemma 4 gives \[\#\{\text{nonempty intermediate buckets}\} = O\left( k\left(\frac{1}{\varepsilon}\right)^D \right),\]
We now state the exact-profile substitute for Lemma 8. Fix an intermediate bucket \(B\) around an anchor \(a\). After applying an isometry sending \(a\) to the origin, write \[u=(r,\xi)\in B, \qquad c=(s,\zeta), \qquad s=d_H(a,c).\] The hyperbolic law of cosines gives \[\cosh d_H(u,c) = \cosh r\cosh s-\sinh r\sinh s\cos\angle(\xi,\zeta).\] Equivalently, \[\cosh d_H(u,c) = \cosh(r-s) + \sinh r \sinh s \bigl(1-\cos\angle(\xi,\zeta)\bigr).\] Define \[h_\zeta(\xi) = -\log\bigl(1-\cos\angle(\xi,\zeta)\bigr).\] Then \[\cosh d_H(u,c) = \cosh(r-s) + \sinh r \sinh s e^{-h_\zeta(\xi)}.\]
Definition 3. Fix a center \(c=(s,\zeta)\), a level \(\lambda\), and an intermediate bucket \(B\). For \(u=(r,\xi)\in B\), set \[T_{s,\zeta}(u) = \sinh r \sinh s e^{-h_\zeta(\xi)}.\] Let \[\delta_0=c_{\mathrm{rd}}\delta,\] where \(c_{\mathrm{rd}}>0\) is a sufficiently small absolute constant. We say that \(u\) is radial-dominant with respect to \((c,\lambda)\) if either \(s\le 2\delta\), or \[T_{s,\zeta}(u) \le \delta_0\cosh d_H(u,c).\] Thus, outside the special case \(s\le 2\delta\), the transverse summand in the exact cosine law contributes only an \(O(\delta)\)-fraction of \(\cosh d_H(u,c).\)
Lemma 11. Let \(B\) be an intermediate bucket around an anchor \(a\). There is a finite family \(\mathcal{F}_{\mathrm{int}}(B)\) of intermediate one-center signatures such that \[|\mathcal{F}_{\mathrm{int}}(B)| = \left(\frac{1}{\varepsilon}\right)^{O(D)}.\] Moreover, for every center \[c\in B_H(a,3R_G)\] and every level \[\frac{R_G}{4}\le \lambda\le 4R_G+1,\] there exists a signature \[\gamma(c,\lambda)\in\mathcal{F}_{\mathrm{int}}(B)\] with score function \[F_\gamma: B \to \mathbb{R}\] such that \[F_\gamma(u) \le d_H(u,c)+\eta_{\mathrm{int}} \qquad \text{for every }u\in B,\] and \[F_\gamma(u) \ge d_H(u,c)-\eta_{\mathrm{int}} \qquad \text{for every }u\in B \text{ satisfying }d_H(u,c) \ge \lambda.\] Here \[\eta_{\mathrm{int}} = C_{\mathrm{int}}\delta = C_{\mathrm{int}}\beta\varepsilon R_G,\] where \(C_{\mathrm{int}}\) is an absolute constant.
Proof. We describe the construction of the signature and the two one-sided estimates. Let \(B\) have radial interval \[r_B^-\le r\le r_B^+\] and angular cap \(U_B\).
First consider the special case \(s=d_H(a,c)\le 2\delta\). Then the triangle inequality gives \[|d_H(u,c)-r|\le s\le 2\delta \qquad \text{for every }u=(r,\xi)\in B.\] In this case we use the radial score \[F_\gamma(u)=r-3\delta.\] It satisfies the upper estimate on all of \(B\), and if \(d_H(u,c)\ge\lambda\), then \[r\ge d_H(u,c)-2\delta,\] so the lower estimate also follows after increasing \(C_{\mathrm{int}}\). We henceforth assume \(s>2\delta\).
Round \(s\) to a value \(\widehat s\) on a mesh of size \(\delta\) in \([0,3R_G]\). Thus \[|s-\widehat s|\le\delta,\] and the number of possible rounded radial values is \[O\left(1+\frac{R_G}{\delta}\right) = O\left(\frac{1}{\varepsilon}\right).\] To control the transverse factor when \(s\) is small, we also record \[\sigma=\log\sinh s.\] Round \(\sigma\) to a value \(\widehat\sigma\) on a mesh of size \(\delta\). Since \(s>2\delta\) and \(s\le 3R_G\), the range of \(\sigma\) is contained in \[[\log\sinh(2\delta),\log\sinh(3R_G)].\] Its length is \[O\left(R_G+\log\left(\frac{e}{\min\{1,\delta\}}\right)\right).\] Because \(\delta=\beta\varepsilon R_G\) and \(R_G \ge R_0\), the number of possible rounded values of \(\sigma\) is \[\left(\frac{1}{\varepsilon}\right)^{O(1)}.\] The rounding gives \[|\sigma-\widehat\sigma|\le\delta, \qquad e^{\widehat\sigma}=e^{O(\delta)}\sinh s.\]
Next, round the level \(\lambda\) to a value \(\widehat\lambda\) on a mesh of size \(\delta\) in \([R_G/4,4R_G+1]\). Since \(R_G \ge R_0\), after increasing the absolute constant \(R_0\) if necessary, this interval has length \(O(R_G)\). Hence the number of rounded levels is \[O\left(\frac{1}{\varepsilon}\right).\]
It remains to record the angular-depth function \(h_\zeta\) on the part of \(U_B\) that can be relevant to the lower estimate at level \(\lambda\). Define \[L_\delta = \begin{cases} \log(e/\delta), & 0<\delta\le 1,\\ 1, & \delta>1. \end{cases}\] For the rounded data \((\widehat s,\widehat\lambda)\), set \[H_B(\widehat s,\widehat\lambda) = r_B^+ + \widehat s - \widehat\lambda + C_0(L_\delta+\delta),\] where \(C_0>0\) is a sufficiently large absolute constant.
We construct the angular record in two cases. If the singular direction \(\zeta\) is separated from \(U_B\) by at least a sufficiently large constant multiple of \(\beta\varepsilon\), then \(h_\zeta\) is smooth on \(U_B\). Since \[\frac{d}{d\varphi} \bigl[-\log(1-\cos\varphi)\bigr] = -\cot(\varphi/2),\] we have \[|\nabla h_\zeta| = O\left(\frac{1}{\varepsilon}\right) \qquad \text{on }U_B.\] Thus a spherical net of mesh \(\Theta(\varepsilon\delta)\) approximates \(h_\zeta\) uniformly on \(U_B\) up to additive error \(O(\delta)\). Its size is \[\left(\frac{1}{\varepsilon}\right)^{O(D)}.\]
It remains to handle the near-ray case, where \(\zeta\) lies within \(O(\beta\varepsilon)\) of \(U_B\). We use local spherical coordinates around \(\zeta\): \[\xi=\exp_\zeta(\varphi\omega), \qquad \varphi=\angle(\xi,\zeta), \qquad \omega\in S_\zeta^{D-2}.\] In these coordinates, \[h_\zeta(\xi) = -\log(1-\cos\varphi),\] so the singular behavior is one-dimensional in \(\varphi\). We divide the truncated depth range \[h_\zeta(\xi)\le H_B(\widehat s,\widehat\lambda)\] into intervals of length \(\delta\). Since \[H_B(\widehat s,\widehat\lambda)=O(R_G+L_\delta)\] and \(\delta=\beta\varepsilon R_G\), the number of depth levels is \[\left(\frac{1}{\varepsilon}\right)^{O(1)}.\] For each depth level, the remaining tangential freedom lies in a \((D-2)\)-dimensional spherical cross-section, and we discretize it by a net of mesh \(\Theta(\varepsilon)\). The possible rounded near-ray directions and the tangential cells together contribute \[\left(\frac{1}{\varepsilon}\right)^{O(D)}\] records in total. Hence the number of near-ray angular records is also \[\left(\frac{1}{\varepsilon}\right)^{O(D)}.\] For the actual direction \(\zeta\), choose an angular record \(\mathcal{A}\) with rounded angular-depth function \[\widehat h_{\mathcal{A}}:U_B\to\mathbb{R}\] satisfying \[|h_\zeta(\xi)-\widehat h_{\mathcal{A}}(\xi)| \le C_h\delta\] whenever \[h_\zeta(\xi)\le H_B(\widehat s,\widehat\lambda).\]
We now define the score function. First define the radial lower score \[R_\gamma(u) = |r-\widehat s|-C_r\delta,\] where \(C_r\) is a sufficiently large absolute constant. On the truncated region, define \(\widetilde{d}_\gamma(u)\) by the rounded exact cosine law \[\cosh \widetilde{d}_\gamma(u) = \cosh(r-\widehat s) + \sinh r e^{\widehat\sigma} e^{-\widehat h_{\mathcal{A}}(\xi)}.\] On the deep tail, \(\widetilde{d}_\gamma(u)\) is not used. To avoid the instability of \(\operatorname{arcosh}\) near \(1\), the exact score is activated only near the rounded level. Define \[E_\gamma(u) = \begin{cases} \widetilde{d}_\gamma(u)-C_s\delta, &\text{if }u\text{ lies in the truncated region and } \widetilde{d}_\gamma(u)\ge \widehat\lambda-C_s\delta, \\ -\infty, & \text{otherwise}, \end{cases}\] where \(C_s\) is a sufficiently large absolute constant. Finally set \[F_\gamma(u) = \max\{R_\gamma(u),E_\gamma(u)\}.\]
We prove the upper estimate first. The radial score satisfies \[R_\gamma(u) \le |r-s|+O(\delta) \le d_H(u,c)+O(\delta)\] for every \(u\in B\). Thus it remains to consider the case where \(E_\gamma(u)>-\infty\). On the truncated region, the rounded data give \[e^{-C\delta}\cosh d_H(u,c) \le \cosh\widetilde{d}_\gamma(u) \le e^{C\delta}\cosh d_H(u,c)\] for an absolute constant \(C>0\). Since \(E_\gamma(u)>-\infty\), we have \[\widetilde{d}_\gamma(u)\ge \widehat\lambda-C_s\delta.\] Using \(|\lambda-\widehat\lambda|\le\delta\) and \(\lambda\ge R_G/4\), and choosing \(\beta\) sufficiently small and \(R_0\) sufficiently large, this implies \[\widetilde{d}_\gamma(u)\ge R_G/8.\] The preceding multiplicative comparison then implies \(d_H(u,c)\ge R_G/16\). On the interval \([R_0/16,\infty)\), the map \(\operatorname{arcosh}\) converts a multiplicative \(e^{O(\delta)}\)-perturbation of \(\cosh d_{H} (u,c)\) into an additive \(O(\delta)\)-perturbation of \(d_H(u,c)\). Hence \[\widetilde{d}_\gamma(u) \le d_H(u,c)+O(\delta),\] and therefore \[E_\gamma(u) \le d_H(u,c)+O(\delta).\] This proves \[F_\gamma(u)\le d_H(u,c)+C\delta\] for every \(u\in B\).
We now prove the lower estimate for points satisfying \(d_H(u,c)\ge\lambda\). If \(u\) is radial-dominant, then either \(s\le 2\delta\), which was already handled, or \[T_{s,\zeta}(u) \le \delta_0\cosh d_H(u,c).\] Since \[\cosh d_H(u,c) = \cosh(r-s)+T_{s,\zeta}(u),\] we obtain \[\cosh(r-s) \ge (1-\delta_0)\cosh d_H(u,c).\] Because \[d_H(u,c)\ge\lambda\ge R_G/4\ge R_0/4,\] the same \(\operatorname{arcosh}\)-stability estimate gives \[|r-s| \ge d_H(u,c)-O(\delta).\] Together with \(|s-\widehat s|\le\delta\), this implies \[R_\gamma(u) \ge d_H(u,c)-O(\delta),\] and hence \[F_\gamma(u) \ge d_H(u,c)-O(\delta).\]
It remains to consider the case where \(u\) is not radial-dominant and \(d_H(u,c)\ge\lambda\). Then \[T_{s,\zeta}(u) > \delta_0\cosh d_H(u,c).\] Since \(d_H(u,c)\ge\lambda\), this gives \[T_{s,\zeta}(u) \ge \exp(\lambda-O(L_\delta)).\] On the other hand, \[T_{s,\zeta}(u) = \sinh r\,\sinh s\,e^{-h_\zeta(\xi)} \le e^{r+s-h_\zeta(\xi)}.\] Therefore \[h_\zeta(\xi) \le r+s-\lambda+O(L_\delta).\] Using \[r\le r_B^+, \qquad |s-\widehat s|\le\delta, \qquad |\lambda-\widehat\lambda|\le\delta,\] and choosing \(C_0\) sufficiently large, we get \[h_\zeta(\xi) \le H_B(\widehat s,\widehat\lambda).\] Thus \(u\) lies in the truncated region. On this region the rounded exact cosine law gives \[|\widetilde{d}_\gamma(u)-d_H(u,c)| \le O(\delta),\] because \(d_H(u,c)\ge\lambda\ge R_G/4\). In particular, \[\widetilde{d}_\gamma(u) \ge \lambda-O(\delta) \ge \widehat\lambda-O(\delta).\] By choosing \(C_s\) sufficiently large, the exact score is active at \(u\). Hence \[E_\gamma(u) = \widetilde{d}_\gamma(u)-C_s\delta \ge d_H(u,c)-O(\delta),\] and therefore \[F_\gamma(u) \ge d_H(u,c)-O(\delta).\] Combining the radial-dominant and non-radial cases proves the lower estimate. Taking \(C_{\mathrm{int}}\) larger than all constants above completes the proof of the two one-sided estimates.
Finally, the number of signatures is the product of the number of rounded radial values, rounded transverse-scale values, rounded levels, and angular records: \[O\left(\frac{1}{\varepsilon}\right) \cdot \left(\frac{1}{\varepsilon}\right)^{O(1)} \cdot O\left(\frac{1}{\varepsilon}\right) \cdot \left(\frac{1}{\varepsilon}\right)^{O(D)} = \left(\frac{1}{\varepsilon}\right)^{O(D)}.\] ◻
The next statement is the intermediate-scale analogue of the large-scale domination lemma. The level used below is the global value \(\Phi_P(C)\), not the maximum over a single bucket. This is the point that makes the restriction \(\lambda\ge R_G/4\) compatible with the lower estimate in Lemma 11.
Lemma 12. Let \(C\subseteq \mathbb{H}^{D}\), \(|C|\le k\), be a center set that covers the anchors at scale \(R_G\), that is, \[\Phi_{A_k}(C)\le R_G.\] Let \[\lambda=\Phi_P(C).\] Then \(\lambda\in [R_G/4,4R_G+1]\). Moreover, let \[p^*\in\operatorname*{argmax}_{p\in P} d_H(p,C).\] If \(p^* \notin A_k\), let \(B^*\) be the intermediate bucket containing \(p^*\). Then there exists an intermediate signature tuple \[\Gamma(C,B^*)\in \mathcal{G}_{\mathrm{int}}(B^*)\] such that, if \[q_{B^*,\Gamma}\in \operatorname*{argmax}_{q\in B^*}F_\Gamma(q),\] then \[\Phi_P(C) \le d_H(q_{B^*,\Gamma},C)+2\eta_{\mathrm{int}} \le \Phi_{P_\varepsilon^{\mathrm{int}}}(C)+2\eta_{\mathrm{int}}.\] If \(p^* \in A_k\), then the same final inequality holds directly.
Proof. Since \(R_G\le 4\mathrm{OPT}_k (P)\) and \(\mathrm{OPT}_k (P) \le \Phi_P (C)\), we have \[\lambda=\Phi_P(C)\ge R_G/4.\] On the other hand, because \(C\) covers the anchors at scale \(R_G\), for every \(p\in P_i\), \[d_H(p,C) \le d_H(p,a_i)+d_H(a_i,C) \le 2R_G.\] Hence \[\lambda=\Phi_P(C)\le 2R_G\le 4R_G+1.\]
Choose \[p^* \in \operatorname*{argmax}_{p\in P}d_H(p,C).\] If \(p^* \in A_k\), then \(p^*\) is retained in \(P_\varepsilon^{\mathrm{int}}\), and the claim is immediate. Otherwise \(p^*\) lies in some nonempty intermediate bucket \(B^*\).
Let \(C_{B^*} \subseteq C\) be the set of centers that are nearest to at least one point of \(B^*\). As in Lemma 5, each center in \(C_{B^*}\) lies in \(B_H(a_i,3R_G)\), where \(a_i\) is the anchor of \(B^*\). Write \[C_{B^*}=\{b_1,\ldots,b_m\}, \qquad 1\le m\le k.\] For each \(b_\ell\), apply Lemma 11 with the common level \(\lambda=\Phi_P(C)\), and choose \[\gamma_\ell=\gamma(b_\ell,\lambda)\in\mathcal{F}_{\mathrm{int}}(B^*).\] If \(m<k\), pad the tuple by repeating \(\gamma_m\), and define \[\Gamma(C,B^*) = (\gamma_1,\ldots,\gamma_m,\gamma_m,\ldots,\gamma_m) \in \mathcal{G}_{\mathrm{int}}(B^*).\]
Since \[d_H(p^*,C)=\lambda,\] we have \[d_H(p^\star,b_\ell)\ge \lambda \qquad \text{for every }\ell.\] Therefore Lemma 11 gives \[F_{\gamma_\ell}(p^*) \ge d_H(p^*,b_\ell)-\eta_{\mathrm{int}} \qquad \text{for every }\ell.\] Taking the minimum over \(\ell\), we obtain \[F_{\Gamma(C,B^*)}(p^*) \ge d_H(p^*,C)-\eta_{\mathrm{int}} = \lambda-\eta_{\mathrm{int}}.\] By the maximality of \(q_{B^*,\Gamma}\), \[F_{\Gamma(C,B^*)}(q_{B^*,\Gamma}) \ge \lambda-\eta_{\mathrm{int}}.\] On the other hand, the upper estimate in Lemma 11 gives \[F_{\Gamma(C,B^*)}(q_{B^*,\Gamma}) \le d_H(q_{B^*,\Gamma},C)+\eta_{\mathrm{int}}.\] Thus \[\lambda \le d_H(q_{B^*,\Gamma},C)+2\eta_{\mathrm{int}} \le \Phi_{P_\varepsilon^{\mathrm{int}}}(C)+2\eta_{\mathrm{int}}.\] Since \(\lambda=\Phi_P(C)\), the claim follows. ◻
For each nonempty intermediate bucket \(B\), define \[\mathcal{G}_{\mathrm{int}}(B) = \mathcal{F}_{\mathrm{int}}(B)^k.\] For \[\Gamma=(\gamma_1,\ldots,\gamma_k) \in \mathcal{G}_{\mathrm{int}}(B),\] define \[F_\Gamma(u) = \min_{h=1,\ldots,k}F_{\gamma_h}(u).\] For every nonempty intermediate bucket \(B\) and every \(\Gamma\in\mathcal{G}_{\mathrm{int}}(B)\), retain one input point \[q_{B,\Gamma} \in \operatorname*{argmax}_{q\in B}F_\Gamma(q).\] The intermediate-scale representative set is \[P_\varepsilon^{\mathrm{int}} = A_k \cup \{q_{B,\Gamma}: B\text{ is a nonempty intermediate bucket},\Gamma\in\mathcal{G}_{\mathrm{int}}(B)\}.\]
The number of nonempty intermediate buckets is \[O\left( k\left(\frac{1}{\varepsilon}\right)^D \right).\] For each bucket \(B\), Lemma 11 gives \[|\mathcal{F}_{\mathrm{int}}(B)| = \left(\frac{1}{\varepsilon}\right)^{O(D)}.\] Therefore \[|\mathcal{G}_{\mathrm{int}}(B)| = |\mathcal{F}_{\mathrm{int}}(B)|^k = \left(\frac{1}{\varepsilon}\right)^{O(kD)}.\] Since the construction stores one representative for each nonempty bucket–signature pair, and also stores the anchors \(A_k\), we have \[|P_\varepsilon^{\mathrm{int}}| \le k+ O\left( k\left(\frac{1}{\varepsilon}\right)^D \right) \cdot \left(\frac{1}{\varepsilon}\right)^{O(kD)} = \left(\frac{1}{\varepsilon}\right)^{O(kD)}.\] Thus, for fixed \(D\), \(k\), and \(\varepsilon\), the intermediate-scale coreset has constant size independent of \(n\) and \(R_G\).
The preprocessing is the same as in the bounded-scale and large-scale constructions: Gonzalez’s farthest-first traversal computes the anchor set \(A_k\), the radius \(R_G\), and the nearest-anchor partition in \(O(kn)\) time. For fixed \(D\), applying the isometry \(\mu_{a_i}\) and computing the polar coordinates \((r_i(p),\xi_i(p))\) of a point \(p\in P_i\) take \(O(1)\) time. The radial shell index is obtained by a single arithmetic operation, and the angular cap index can be found in \(O(1)\) time after fixed-parameter preprocessing depending only on \(D\) and \(\varepsilon\). Thus all points can be assigned to their intermediate buckets in \(O(n)\) time after the nearest-anchor partition is known.
During a scan of the input, whenever a point \(p\in B\) is encountered, the algorithm evaluates \(F_\Gamma(p)\) for every \(\Gamma \in \mathcal{G}_{\mathrm{int}}(B)\) and updates the current maximizer \(q_{B,\Gamma}\). Since \[F_\Gamma(p) = \min_{h=1,\ldots,k}F_{\gamma_h}(p),\] one evaluation of \(F_\Gamma(p)\) takes \(O(k)\) time. Hence the work charged to one input point is \[O\left( k\left(\frac{1}{\varepsilon}\right)^{O(kD)} \right).\] Summing over all input points, and including the initialization of all bucket–signature maximizers, the total intermediate-scale construction time is \[O(kn)+O(n)+ O\left( nk\left(\frac{1}{\varepsilon}\right)^{O(kD)} \right) = O\left( nk\left(\frac{1}{\varepsilon}\right)^{O(kD)} \right).\] In particular, for fixed \(D\), \(k\), and \(\varepsilon\), the intermediate-scale coreset can be constructed in \(O(n)\) time.
Theorem 8 (Intermediate-scale continuous \(k\)-center coreset). Let \(D\ge 1\), let \(0<\varepsilon<1\), and let \(P\subset\mathbb{B}^{D}\) be finite. Run Gonzalez’s farthest-first traversal for \(k\) steps, and let \[A_k=\{a_1,\ldots,a_k\}, \qquad R_G=\Phi_P(A_k).\] Assume that \[R_0 \le R_G \le R_1.\] Construct \(P_\varepsilon^{\mathrm{int}}\subseteq P\) by the intermediate-scale shell–cone exact-profile construction above. Let \[C_{P_\varepsilon^{\mathrm{int}}} \in \operatorname*{argmin}_{\substack{C\subseteq\mathbb{H}^{D}\\ |C|\le k}} \Phi_{P_\varepsilon^{\mathrm{int}}}(C)\] be an optimal continuous \(k\)-center solution for \(P_\varepsilon^{\mathrm{int}}\). Then \[\Phi_P(C_{P_\varepsilon^{\mathrm{int}}}) \le (1+\varepsilon)\mathrm{OPT}_k(P).\] Moreover, \[|P_\varepsilon^{\mathrm{int}}| = \left(\frac{1}{\varepsilon}\right)^{O(kD)},\] and the construction time is \[O\left( nk\left(\frac{1}{\varepsilon}\right)^{O(kD)} \right).\] Consequently, for fixed \(D\), \(k\), and \(\varepsilon\), the intermediate-scale coreset can be constructed in \(O(n)\) time.
Proof. Let \[C_{\mathrm{red}} = C_{P_\varepsilon^{\mathrm{int}}}.\] First, \(C_{\mathrm{red}}\) covers the anchors at scale \(R_G\). Indeed, since \(A_k\subseteq P_\varepsilon^{\mathrm{int}}\), and since \(A_k\) itself is a feasible set of \(k\) centers for the reduced instance, \[\Phi_{P_\varepsilon^{\mathrm{int}}}(C_{\mathrm{red}}) \le \Phi_{P_\varepsilon^{\mathrm{int}}}(A_k) \le \Phi_P(A_k) = R_G.\] Thus \[\Phi_{A_k}(C_{\mathrm{red}}) \le R_G.\] By Lemma 12, \[\Phi_P(C_{\mathrm{red}}) \le \Phi_{P_\varepsilon^{\mathrm{int}}}(C_{\mathrm{red}}) + 2\eta_{\mathrm{int}}.\] Let \(C^*\) be an optimal continuous \(k\)-center solution for \(P\). Since \[P_\varepsilon^{\mathrm{int}}\subseteq P,\] we have \[\Phi_{P_\varepsilon^{\mathrm{int}}}(C^*) \le \Phi_P(C^*) = \mathrm{OPT}_k(P).\] By the optimality of \(C_{\mathrm{int}}\) on the reduced instance, \[\Phi_{P_\varepsilon^{\mathrm{int}}}(C_{\mathrm{int}}) \le \Phi_{P_\varepsilon^{\mathrm{int}}}(C^*) \le \mathrm{OPT}_k(P).\] Therefore \[\Phi_P(C_{\mathrm{int}}) \le \mathrm{OPT}_k(P)+2\eta_{\mathrm{int}}.\] Since \[\eta_{\mathrm{int}} = C_{\mathrm{int}}\beta\varepsilon R_G\] and Lemma 1 gives \[R_G\le 4\mathrm{OPT}_k(P),\] we obtain \[2\eta_{\mathrm{int}} = 2C_{\mathrm{int}}\beta\varepsilon R_G \le 8C_{\mathrm{int}}\beta\varepsilon\mathrm{OPT}_k(P).\] Choosing \(\beta>0\) sufficiently small so that \[8C_{\mathrm{int}}\beta\le 1,\] we get \[2\eta_{\mathrm{int}} \le \varepsilon\mathrm{OPT}_k(P).\] Hence \[\Phi_P(C_{\mathrm{red}}) \le (1+\varepsilon)\mathrm{OPT}_k(P),\] as claimed. ◻
In this paper, we study coresets for the continuous \(k\)-center problem in hyperbolic space. Crucially, our coreset reduces the input data points to a smaller set \(P_\varepsilon\), while allowing the centers to be placed anywhere in the continuous hyperbolic space. This distinction is vital: we do not restrict the search space for centers. We employ a metric-transfer principle to prove that, because our coreset faithfully mimics the distance properties of the original input at a fine scale, an optimal solution found on the coreset remains near-optimal for the full dataset.
Our construction handles three distinct scale regimes. In the bounded-scale regime (\(R_G \le R_0\)), each nearest-anchor cluster resides within a small, bounded hyperbolic ball. By shifting the corresponding anchor to the origin in the Poincaré ball model, we ensure that the local hyperbolic metric behaves like the standard Euclidean metric. This allows us to construct a coreset simply by applying a local grid, yielding a size of \(O(k/\varepsilon^D)\). In the large-scale regime (\(R_G \ge R_1\)), applying a standard grid is infeasible because the volume of hyperbolic space grows exponentially with the radius. To circumvent this, we decompose the input around farthest-first anchors into radial shells and angular cones. By storing only one representative point per bucket-profile pair, e obtain a coreset whose size is independent of the total radius. This yields a coreset of size \(O(k(1/\varepsilon)^{(k+1)D+k})\). Finally, the intermediate-scale regime (\(R_0 \le R_G \le R_1\)) is handled by a shell-cone decomposition using the precise hyperbolic law of cosines rather than the coarse approximations used in large-scale settings. In all scale regimes, solving the \(k\)-center problem on our coreset yields a \((1+\varepsilon)\)-approximation to the original input. The construction requires \(O(nk(1/\varepsilon)^{O(kD)})\) time, which is linear in terms of the number of points \(n\). Crucially, our coreset size remains constant regardless of the input size \(n\) or the spatial extent (radius) of the data.
Several questions remain open:
It is currently unknown if the size \((1/\varepsilon)^{O(kD)}\) is optimal. Establishing lower bounds for hyperbolic \(k\)-center coresets is a significant open problem.
There is a gap between our bound and the more compact \(O((k/\varepsilon)^D)\) bound seen in Euclidean spaces. Future research is needed to determine if this exponential dependence on \(k\) is intrinsic to hyperbolic geometry or if refined structural theorems can reduce it.
Our method is designed for the continuous \(k\)-center problem. The discrete version—where centers must be chosen from the input set—requires a different structural principle, as our current coreset preserves demand points but not necessarily the set of optimal candidate centers.