# Uniform Page Migration Problem in Euclidean Space
## 3 Algorithm and Its Upper Bound Analysis  
We focus on the page size \(D=1\) and the metric space \(\mathbb{R}^{n}\) under \(L^{2}\) norm \(\delta\) for \(n\geq 1\). We state our deterministic algorithm, called PQ, in the following paragraph. Intuitively, the algorithm determines the location of the page using two locations from previous requests. We prove the competitiveness of 2.75, claimed in Theorem 1, using a potential function \(\Phi\). As mentioned in Section 2, defining suitable events and showing that \(\Delta cost_{PQ}+\Delta\Phi\leq 2.75\Delta cost_{OPT}\) for any defined event is sufficient. For the proof of the theorem, we need to show an inequality different from a triangle inequality. We separately provide a technical part for that inequality as Lemma 1. The lemma is about points computed by the algorithm. Algorithm PQ. _This algorithm maintains the server at the center of two points \(p\) and \(q\), both of which are initially located at the initial server location. Upon each request at location \(r\), if \(\delta\left(p,r\right)\geq\delta\left(q,r\right)\), then \(p\) moves to \(r\); otherwise, \(q\) moves to \(r\). The algorithm migrates its server to \(s=\frac{p+q}{2}\) after \(p\) or \(q\) moves._  
**Lemma 1**. : _For any \(\rho>2\) and \(p,q,r,s\in\mathbb{R}^{2}\) such that \(p\
eq q\), \(\delta\left(p,r\right)\geq\delta\left(q,r\right)>0\), and \(s\) is the center of \(p\) and \(q\), \(g=\delta\left(s,r\right)-\left(\frac{\rho}{2}-\frac{1}{2}\right)\cdot\delta \left(p,r\right)-\left(\frac{\rho}{2}-1\right)\cdot\left(\delta\left(q,r \right)-\delta\left(p,q\right)\right)\) is maximized if \(\delta\left(p,r\right)=\delta\left(q,r\right)\), or \(\delta\left(p,q\right)=\delta\left(p,r\right)+\delta\left(q,r\right)\), or \(\delta\left(p,r\right)=\delta\left(p,q\right)+\delta\left(q,r\right)\)._  
Proof. : We may assume without loss of generality that \(p=\left(-1,0\right),\)\(s=\left(0,0\right),\)\(q=\left(1,0\right),\) and \(r=\left(\ell\cos\theta,\)\(\ell\sin\theta\right)\) with \(0\leq\theta\leq\pi/2\). Moreover, we fix \(\delta\left(s,r\right)=\ell\) and regard \(g\) as a function of \(\theta\). The aim is to prove that \(g\) is maximized at \(\theta=0\) or \(\theta=\pi/2\). It follows that:  
\[\delta\left(p,r\right) =\sqrt{\left(\ell\cos\theta+1\right)^{2}+\ell^{2}\sin^{2}\!\theta} =\sqrt{\ell^{2}+2\ell\cos\theta+1}\] \[\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}\] \[\frac{d\delta\left(p,r\right)}{d\theta} =\frac{-\ell\sin\theta}{\sqrt{\ell^{2}+2\ell\cos\theta+1}}=-\frac{ \ell\sin\theta}{\delta\left(p,r\right)}\]\[\frac{d\delta\left(q,r\right)}{d\theta}=\frac{\ell\sin\theta}{\sqrt{\ell^{2}-2\ell \cos\theta+1}}=\frac{\ell\sin\theta}{\delta\left(q,r\right)}\]  
Therefore, we have  
\[\frac{dg}{d\theta}=\ell\sin\theta\left\{\frac{\rho-1}{2}.\frac{1}{\delta\left(p,r\right)}-\left(\frac{\rho}{2}-1\right)\cdot\frac{1}{\delta\left(q,r\right)} \right\}=\frac{\left(\rho-1\right)\cdot\ell\cdot\sin\theta}{2\delta\left(q,r \right)}\left\{\frac{\delta\left(q,r\right)}{\delta\left(p,r\right)}-\frac{ \rho-2}{\rho-1}\right\}\]  
\(\frac{\delta\left(q,r\right)}{\delta\left(p,r\right)}=\sqrt{\frac{\ell^{2}-2 \ell\cos\theta+1}{\ell^{2}+2\ell\cos\theta+1}}\) monotonically increases from \(\frac{\left|\ell-1\right|}{\ell+1}\) to \(1\) as \(\theta\) changes from \(0\) to \(\pi/2\). If \(\frac{\left|\ell-1\right|}{\ell+1}\geq\frac{\rho-2}{\rho-1}\), then \(\frac{dg}{d\theta}\geq 0\) for any \(\theta\). Therefore, \(g\) is maximized at \(\theta=\pi/2\). Otherwise, since \(0<\frac{\rho-2}{\rho-1}<1\), there exists \(0<t<\pi/2\) such that \(\sqrt{\frac{\ell^{2}-2\ell\cos t+1}{\ell^{2}+2\ell\cos t+1}}=\frac{\rho-2}{ \rho-1}\). Since \(\frac{dg}{d\theta}\geq 0\) for \(\theta\geq t\) and \(\frac{dg}{d\theta}\leq 0\) for \(\theta<t\), \(g\) is maximized at \(\theta=0\) or \(\theta=\pi/2\). **Theorem 1**. : _PQ is \(\rho\)-competitive for \(\rho=\frac{11}{4}\) and the page size \(D=1\)._  
Proof.