# Sphere Fitting with Applications to Machine Tracking
## 2 Methods
### Algorithms
#### 2.3.1. Optimal Solution for the Median-Sphere  
In order to solve the median-sphere problem we restate the problem as _real polynomial system_. Let \(p\in\mathbb{R}^{d}\), and \(S\in\mathbb{S}^{d-1}\) be a sphere of radius \(r>0\) which is centered at \(x\in\mathbb{R}^{d}\). Hence, \(\operatorname{dist}(p,S)=\|p-x\|-r\mid\) is the distance between \(p\) and \(S\). That is, \(\operatorname{dist}(p,S)=r-\|p-x\|\) if the point \(p\) is inside the sphere, and \(\operatorname{dist}(p,S)=\|p-x\|-r\) if the point \(p\) is outside the sphere.  
In what follows, \(\text{sgn}(p,S)\) denotes the sign of \(\text{dist}(p,S)\). More precisely, \(\text{sgn}(p,S)=1\) if \(\|p-x\|\geq r\), and \(\text{sgn}(p,S)=-1\) otherwise. Therefore,  
\[\text{dist}(p,S)=|\ \|p-x\|-r\ |\] \[\Rightarrow\ \begin{array}{l}r+\text{dist}(p,S)=\|p-x\|\ \text{if}\ \|p-x\|\geq r\ \text{and}\\ r-\text{dist}(p,S)=\|p-x\|\ \text{if}\ \|p-x\|<r\end{array}\.\]  
Recall that the number that minimizes the sum of distances to a set of numbers is a median of this set. Hence, \(\text{opt}_{1}(P)\) is a sphere that minimizes the sum of distances to the input points, and so must separate \(P\) such that the difference between the number of points inside the sphere and the number of points outside the sphere must be less than the number of points that are placed on the sphere. That is, the number of possible permutations for constructing a set of equations (i.e., to determine a possible sign for each point) is limited by the number of spheres that can be defined using a tuple of \(d+1\) points, i.e., \(n^{(d+1)}\) spheres. Hence, we define a solution for the median-sphere problem by finding the sphere that minimizes the sum of distances to each of the \(n^{(d+1)}\) polynomial systems, each consisting of \(n\) equations. The optimum among these polynomial systems is the \(S^{*}\in\mathbb{S}^{d-1}\) (that is defined by its center \(x^{*}\) and radius \(r^{*}\)) that minimizes the sum of distances \(\sum_{i=1}^{n}\text{dist}(p_{i},S^{*})\).  
In Algorithm 1, we present such algorithm for the median sphere.  
Let \(P\) be a set of \(n\) points in \(\mathbb{R}^{d}\). We denote by \(P^{d+1}\) a tuple of \(d+1\) different points from \(P\). We denote by \(\textsc{sphere}(P^{d+1})\) the \(d\)-dimensional sphere that defined by \(P^{d+1}\). We denote by \(\textsc{polynomial}(P,u,S)\) a system of \(n\) equations (polynomial system) that optimizes the median-sphere problem. We denote by \(\textsc{solver}(f)\) an optimization for polynomial system \(f\), e.g., using Maple [31] or Wolfram Alpha [32], etc...  
```
Input: A set \(P=\{p_{1},p_{2},\ldots,p_{n}\}\subseteq\mathbb{R}^{d}\) of points,  a weight function \(u:P\rightarrow[0,\infty)\). Output: A median-sphere \(S^{*}\).
1 Set \(S^{*}=\)Sphere(\(\{p_{1},p_{2},\ldots,p_{d+1}\}\in P\)) // Default median-sphere
2 forevery\(P^{d+1}\subseteq P\)do
3 Set \(S^{\prime}=\)sphere(\(P^{d+1}\))
4 Set \(f:=\)polynomial(\(P^{d+1},u,S^{\prime}\))
5 Set \(S=\)solver(\(f\))
6 if\(\text{Cost}(P,S^{*})<\text{Cost}(P,S)\)then
7 Set \(S^{*}=S\)
8 Return\(S^{*}\)
```  
**Algorithm 1**MedianSphere(\(P,u\))  
Clearly, such a solution is not applicable to a large set of points. Instead, we offer the following solution in Algorithm 2 (MedianSphereCoreset), which reduces the amount of data and then runs the existing solution on the resulting small set, called a coreset.