# Uniform Page Migration Problem in Euclidean Space
## 3 Algorithm and Its Upper Bound Analysis
: We use the following potential function for OPT's server location \(t\), PQ's server \(s\), and point locations \(p\) and \(q\):  
\[\Phi=\frac{\rho}{2}\cdot\left(\delta\left(p,t\right)+\delta\left(q,t\right) \right)-\frac{\rho-2}{2}\cdot\delta\left(p,q\right)\]  
We separate the online events into two parts. The first is to consider only the migration costs incurred by OPT's server, and the second is to consider the service costs incurred by OPT together with the migration and service costs incurred by PQ. It is sufficient to show that the inequality \(\Delta cost_{PQ}+\Delta\Phi\leq\rho\cdot\Delta cost_{OPT}\) follows in both parts, upon each request located at \(r\). _Part 1._ The migration of OPT's server from \(t\) to \(t\prime\) induces a change of \(\delta\left(t,t^{\prime}\right)\) to the total cost of the optimal algorithm OPT but no change to the cost incurred by PQ. The total change of \(\Phi\) is then \(\frac{\rho}{2}\cdot\left(\delta\left(p,t^{\prime}\right)-\delta\left(p,t \right)+\delta\left(q,t^{\prime}\right)-\delta\left(q,t\right)\right)\). Therefore, it is sufficient to show the following inequality:  
\[\frac{\rho}{2}\delta\left(p,t^{\prime}\right)-\frac{\rho}{2}\delta\left(p,t \right)+\frac{\rho}{2}\delta\left(q,t^{\prime}\right)-\frac{\rho}{2}\delta \left(q,t\right)\leq\frac{\rho}{2}\delta\left(t,t^{\prime}\right)+\frac{\rho} {2}\delta\left(t,t^{\prime}\right)\]  
This follows by the symmetry of the distance function \(\left(\delta\left(a,b\right)=\delta\left(b,a\right)\right)\) and the triangle inequalities \(\delta\left(p,t^{\prime}\right)\leq\delta\left(t,t^{\prime}\right)+\delta \left(p,t\right)\) and \(\delta\left(q,t^{\prime}\right)\leq\delta\left(t,t^{\prime}\right)+\delta \left(q,t\right)\). _Part 2._ We may assume, without loss of generality, that \(\delta\left(p,r\right)\geq\delta\left(q,r\right)\). By this assumption, PQ moves \(p\) to \(r\). Since PQ maintains its server at the center of \(p\) and \(q\), the migration cost incurred by PQ is then \(\frac{1}{2}\delta\left(p,r\right)\). For this part, we have the following equalities:  
\[\Delta cost_{PQ}=\delta\left(s,r\right)+\frac{1}{2}\delta\left(p,r\right)\]  
\[\Delta\Phi=\frac{\rho}{2}\cdot\left(\delta\left(r,t\right)-\delta\left(p,t \right)\right)+\left(\frac{\rho}{2}-1\right)\cdot\left(\delta\left(p,q\right)- \delta\left(q,r\right)\right)\]  
\[\Delta cost_{OPT}=\delta\left(t,r\right)\]  
Therefore, we shall show the following inequality:  
\[\delta\left(q,r\right) =\sqrt{\left(\ell\cos\theta-1\right)^{2}+\ell^{2}\sin^{2}\!\theta} =\sqrt{\ell^{2}-2\ell\cos\theta+1}\]0  
Since \(\delta\left(r,t\right)+\delta\left(p,t\right)\geq\delta\left(p,r\right)\), it is sufficient to show:  
\[\delta\left(q,r\right) =\sqrt{\left(\ell\cos\theta-1\right)^{2}+\ell^{2}\sin^{2}\!\theta} =\sqrt{\ell^{2}-2\ell\cos\theta+1}\]1This follows for the cases \(p=q\) and \(q=r\), because \(s=p=q\) and \(\delta\left(s,r\right)=\frac{1}{2}\)\(\delta\left(p,r\right)\), respectively. We assume \(p\
eq q\) and \(q\
eq r\). It is sufficient to show that the maximum value of the left-hand side of Equation (1) is less than or equal to zero. If we regard \(p\), \(q\), \(r\), and \(s\) as vectors in \(\mathbb{R}^{n}\), then at most three vectors of them, say \(p\), \(q\), and \(r\), are independent. Therefore, the points \(p\), \(q\), \(r\), and \(s\) are on a plane in \(\mathbb{R}^{n}\). Applying Lemma 1 on this plane, the left-hand side of Equation (1) is maximized in one of three situations. Situation 1: \(\delta\left(p,r\right)=\delta\left(q,r\right)\), Situation 2: \(\delta\left(p,q\right)=\delta\left(p,r\right)+\delta\left(r,q\right)\), or Situation 3: \(\delta\left(p,r\right)=\delta\left(p,q\right)+\delta\left(q,r\right)\). We proceed to show inequality (1) for each of these three situations. _Situation 1_: Substitution of \(\delta\left(p,q\right)\) by \(2\cdot\delta\left(s,q\right)\) in Equation (1) reveals the following inequality.