# Uniform Page Migration Problem in Euclidean Space
## 4 A Lower Bound for PQ  
In this section, we show that the exact competitiveness of the algorithm is greater than \(2.732\). We introduce an adversary through Theorem 2 and prove the existence of such a lower bound. The adversary makes a special sequence of requests on \(\mathbb{R}^{2}\) against the proposed algorithm. The requests are given at vertices of a triangle that tends to be equilateral. After the second request, the server repeatedly migrates between the center points of two sides of the triangle.  
**Theorem 2**.: _For a sufficiently large integer \(n\), there exist a request sequence \(\sigma=r_{1},\ldots,r_{2n+1}\), three request locations \(a,b\), and \(s\) on a plane, and the initial server location \(s\), such that \(\mathit{cost}_{PQ}\left(s,\sigma\right)\geq\rho\cdot\mathit{cost}_{OPT}\left(s, \sigma\right)\) for \(\rho=1+\sqrt{3}\approx 2.732\)._Proof.: We describe our approach before more technical discussion in the subsequent paragraphs. In Figure 1, we illustrate the behavior of PQ against requests by our adversary. We assume that \(\delta\left(s,b\right)\) is slightly larger than \(\delta\left(s,a\right)=\delta\left(b,a\right)\). Points \(u\) and \(v\) are the centers of \(a\) and \(s\), and \(a\) and \(b\), respectively. For requests \(a,\ b,\ s,\ b,\ s,\ b,\ s,\ \ldots\), PQ migrates its server along the dashed line, because \(p\) does not move from \(a\). A request occurs at \(b\) when the server is at \(u\), and a request occurs at \(s\) when the server is at \(v\). Note that \(a\), \(b\), and \(s\) tend to be the vertices of an equilateral triangle as \(\delta\left(s,b\right)\) approaches \(\delta\left(s,a\right)=\delta\left(b,a\right)\).  
For \(r_{1}=a,r_{2k}=b\), and \(r_{2k+1}=s\), where \(1\leq k\leq n\) and \(a\), \(b\), and \(s\) are the vertices of an equilateral triangle with a unit side length, the cost of the optimal algorithm \(cost_{OPT}\left(s,\sigma\right)\) is at most \(n+1\) by keeping the server at the initial location \(s\).  
The adversary infinitesimally perturbs the distances by slightly increasing the distance between \(s\) and \(b\). Upon the first request at \(a\), PQ serves the request by the cost of \(\delta\left(s,a\right)\) and migrates the server to \(u\), which is the center of \(s\) and \(a\), by the cost of \(\delta\left(s,u\right)\). This is because point \(p\) at \(s\) moves to \(a\). The \(2\)th request at \(b\) is served with the cost of \(\delta\left(u,b\right)\), causing point \(q\) at \(s\) to move to \(b\), and the server migrates to \(v\), which is at the center of \(a\) and \(b\), with the cost of \(\delta\left(u,v\right)\). The \((2k+1)\)st request at \(s\) is served with the cost of \(\delta\left(v,s\right)\). The point \(q\) at \(b\) moves to \(s\); hence, the server migrates to \(u\) with the cost of \(\delta\left(u,v\right)\).  
We compute the total cost of PQ by using the distances of the unperturbed triangle, since the actual distances (and hence the actual costs of PQ and OPT) may differ by an infinitesimally small amount from these computations. Therefore, we have  
\[cost_{PQ}\left(s,\sigma\right)=\delta\left(s,a\right)+\delta\left(s,u\right)+ n\cdot\left(\delta\left(u,b\right)+\delta\left(u,v\right)+\delta\left(v,s \right)+\delta\left(v,u\right)\right)\approx 1.5+\left(\sqrt{3}+1\right)n\]  
Since  
\[\lim_{n\rightarrow\infty}\frac{1.5+\left(\sqrt{3}+1\right)n}{n+1}=\sqrt{3}+1\]  
then \(\frac{cost_{PQ}\left(s,\sigma\right)}{cost_{OPT}\left(s,\sigma\right)}\) is at least \(2.732\). This completes the proof.