# Sphere Fitting with Applications to Machine Tracking
## 2 Methods
### Analysis  
In this section, we analyze the algorithms of the previous section in terms of time complexity, coreset's size and the quality of the approximation. The approximation that is states in Theorem 2 that follows is with respect to the optimal solution \(\operatorname{opt}_{1}(P,u)\) such that the calculated cost of our (sphere) solution is compared directly with the calculated cost of the optimal (sphere) solution.  
**Theorem 2**.: _Let \(P\) be a set of \(n\) points in \(\mathbb{R}^{d}\). Let \(\varepsilon,\delta\in(0,1)\). Let \((C,w)\) be the output of a call to \(\operatorname{MedianSphereCoreset}(P,u,\varepsilon)\), see Algorithm 2. Then, with probability at least \(1-\delta\), \((C,w)\) is an \(\varepsilon\)-coreset of \(P\) for the median-sphere. Moreover, \((C,w)\) consists of \(O(d^{2}\log^{2}(n)\log(1/\delta)/\varepsilon^{2})\) points, and can be computed in \(O(dn^{2}+n/(d\varepsilon^{3d})+(d^{2}\log^{2}(n)\log(1/\delta))/\varepsilon^{2})\) time._  
**Proof of Theorem 2.**  
_Coreset's size:_  
By Line 8 of Algorithm 2, the size of the coreset is \(|C|=O((d^{2}\log^{2}(n)\log(1/\delta))/\varepsilon^{2})\).  
_Running time of coreset's construction:_  
Algorithm 2 has two steps. In the first step the algorithm calculates the sensitivity for every point \(p\in P\). That is, runs \(\lceil n/(d+2)\rceil\) iterations for picking \(d+2\) points (Algorithm 3), each in \(O(nd+1/\varepsilon^{3d})\) time. Therefore, the total time of the first step is \(O(dn^{2}+n/(d\varepsilon^{3d}))\) time. In the second step the algorithm picks \(O(d^{2}\log^{2}(n)\log(1/\delta)/\varepsilon^{2})\) points. Hence, the running time of Algorithm 2 is \(O(dn^{2}+n/d\varepsilon^{3d}+(d^{2}\log^{2}(n)\log(1/\delta))/\varepsilon^{2})\).  
Accuracy:Our proof uses the technique of [37] to bounds the maximum distance of each point in \(P\) to any sphere.  
Let \(c=\lceil n/(d+2)\rceil\) be the total number of iterations of the \"while\" loop in Lines 2-7. For every integer \(i\in[1,c]\). let \(Q_{i}:=Q\) (Line 3) be the output of ThinnestSphereCoreset(\(P\)) at the \(i\)-th iteration. That is, \(Q_{i}\) defines concentric external and internal spheres that bounds the remaining set \(P\). Therefore, by the triangle inequality, we can bound the maximum distance from \(P\setminus Q_{i}\) to \(Q_{i}\) by  
\[\max_{p\in P\setminus Q_{i}}\operatorname{dist}(p,S)\leq(1+\varepsilon)\max_ {q\in Q_{i}}\operatorname{dist}(q,S).\]  
Therefore, we can bound the sensitivity of every point \(q\in Q_{i}\) by  
\[s(q)=\frac{\operatorname{dist}(q,S)}{\sum_{p\in P}\operatorname{ dist}(p,S)}\leq\frac{\operatorname{dist}(q,S)}{\sum_{j=1}^{i}\max_{p\in Q_{j}} \operatorname{dist}(p,S)}\leq\frac{1}{i(1-\varepsilon)},\]  
where the first inequality holds since the right denominator is a subset of the left denominator, and the second inequality holds since the numerator is uphold \(1-\varepsilon\) of the denominator by definition. Hence, the total sensitivity is  
\[\sum_{p\in P}s(p)=\sum_{i=1}^{c}\frac{|\,Q_{i}\mid}{i(1-\varepsilon)}<\frac{( d+2)\log_{2}n}{(1-\varepsilon)}=O\left(\frac{d\log n}{1-\varepsilon}\right),\]  
where the first equality holds by Line 5 of Algorithm 2. The middle inequality refers to the size of Algorithm 3. The right equality holds by a trivial geometric sequence.  
Substituting in Theorem 1 the input set \(P\), the VC-dimension \(d^{\prime}=(d+2)\), which raised from a trivial classification (cardinality of the largest set of points that the algorithm can shatter), and the query set \(Q=\mathbb{S}^{d-1}\), yield that with probability at least \(1-\delta\), the pair \((C,w)\) is an \(\varepsilon\)-coreset of \(P\) for median sphere, and therefore, the size of our coreset is \(O(d^{2}\log^{2}(n)\log(1/\delta)/\varepsilon^{2})\).