# Sphere Fitting with Applications to Machine Tracking
## 2 Methods
### Algorithms
#### 2.3.2 Coreset Construction  
In order to reduce the number of input points, we suggest Algorithm 2 (called MedianSphereCoreset) to construct a coreset for the median sphere by removing layers of the thinnest-sphere surface using Algorithm 3 (ThinnestSphereCoreset). We first give a formal definition for such a coresets.  
**Definition 2** (Coreset for median-sphere).: _Let \(P\subseteq\mathbb{R}^{d}\) be a finite set of points, and \(u:P\to[0,\infty)\) be a weight function. For \(\varepsilon\in[0,1)\), \(C\subseteq P\), and a weight function \(w:C\to(0,\infty)\), the pair \((C,w)\) is an \(\varepsilon\)-coreset for the median-sphere of \(P\) if for every sphere \(S\in\mathbb{S}^{d-1}\)_  
\[|\ \mathrm{cost}(P,u,S)-\mathrm{cost}(C,w,S)\ |\leq\varepsilon\cdot\mathrm{cost}(P,u,S).\]  
**Definition 3** (coreset for thinnest-sphere).: _Let \(P\subseteq\mathbb{R}^{d}\) be a finite set of points. A subset \(C\subseteq P\), is an \(\varepsilon\)-coreset for the thinnest-sphere of \(P\) if for every sphere \(S\in\mathbb{S}^{d-1}\),_  
\[\max_{q\in C}\mathrm{dist}(q,S)\geq(1+\varepsilon)\max_{p\in P}(p,S).\]  
For every point \(p\in P\), we define the sensitivity [33; 34] of \(p\) with respect to every sphere \(S\in\mathbb{S}^{d-1}\) as its relative contribution to the overall \(\mathrm{cost}(P,u,S)\),  
\[s(p)=\sup\frac{\mathrm{dist}(p,S)}{\sum_{q\in P}\mathrm{dist}(q,S)}.\]  
Here we assume that the sup is over every \(S\in\mathbb{S}^{d-1}\) such that \(\sum_{q\in P}\mathrm{dist}(q,S)>0\).  
**Definition 4** (Query space [35]).: _Let \(P\) be a finite set, \(u:P\to[0,\infty)\) be a weight function, and \(P^{\prime}=(P,u)\) denote a weighted set. Let \(Q\) be a (possibly infinite) set called query set, \(f:P\times Q\to[0,\infty)\) be called a cost function, and loss be a function that assigns a non-negative real number for every real vector. The tuple \((P^{\prime},Q,f,\mathrm{loss})\) is called a query space. For every \(q\in Q\) we define the overall fitting error of \(P^{\prime}\) to \(q\) by_  
\[f_{\mathrm{loss}}(P^{\prime},q):=\mathrm{loss}((u(p)f(p,q))_{p\in P})=\]  
\[\mathrm{loss}(u(p_{1})f(p_{1},q),\ldots,u(p_{n})f(p_{n},q)).\]  
The dimension of a query space \((P,u,\mathbb{S}^{d-1},\mathrm{cost})\) is the VC-dimension of the range space that it induced, as defined below. The classic VC-dimension was defined for sets and subset and here we generalize it to query spaces, following [34].  
**Definition 5** (Dimension for a query space [34; 35; 36]).: _For a set \(P\) and set ranges of subsets of \(P\), the VC-dimension of (\(P\), ranges) is the size \(|C|\) of the largest subset \(C\subseteq P\) such that_  
\[|\ \{C\cap range\ |\ range\in ranges\}\ |=2^{|C|}.\]  
It was proven in [35] that an \(\varepsilon\)-coreset can be obtained for a given problem (e.g., median-sphere), with high probability, by sampling points i.i.d. from the input points with respect to their sensitivity. Then we assign each sample point with a weight that is inverse proportional to its sensitivity. The number of sampled points should be proportional to the VC-dimension of the query space and the sum of sensitivities \(\sum_{p\in P}s(p)\). Formally,  
**Theorem 1**.: _Let \(((P,u),Q,f,\|\cdot\|_{1})\) be a query space of dimension \(d^{\prime}\), and let \(n\) be the size of \(P\). Let \(s:P\to(0,1)\) be a sensitivity function for every \(p\in P\), and let \(t=\sum_{p\in P}s(p)\) be the total sensitivity of the set \(P\). Let \(\varepsilon,\delta\in(0,1)\). Let \(c>0\) be a universal constant that can be determined from the proof [35]. Let_  
\[m\geq\frac{c(t+1)(d^{\prime}(\log t+\log(1/\delta))}{\varepsilon^{2}}.\]  
_There is an algorithm \(\textsc{Coreset}(P,u,s,m)\) in [35] that outputs weighted set \((C,w)\) such that \(|\ C|=m\), and, with probability at least \(1-\delta\), \((C,w)\) is an \(\varepsilon\)-coreset for \(((P,u),Q,f,\|\cdot\|_{1})\)._In Algorithm 2, we present such a coreset construction for the median sphere.