## 4 Construction of a Finite Set of Triangles  
For triangle \(\Delta_{1}=\Delta(1,a,b)\) and \(d>0\), let \(\Delta_{2}=\Delta(1,a^{\prime},b^{\prime})\) be any triangle such that \(a-d\leq a^{\prime}\leq a\) and \(b-d\leq b^{\prime}\leq b\). Then as shown in Sec. 2 the competitive ratio for \(\Delta_{2}\), denoted by \(f(\Delta_{2})\), can be written as  
\[f(\Delta_{2})\leq\max\left(\frac{a}{a^{\prime}},\frac{b}{b^{\prime}}\right)f( \Delta_{1})\leq\max\left(\frac{a}{a-d},\frac{b}{b-d}\right)f(\Delta_{1})\leq \frac{a}{a-d}f(\Delta_{1}).\](The last inequality comes from the fact that \(a\leq b\).) Recall that triangle \(\Delta(1,a,b)\) always satisfies \(1\leq a\leq b\leq a+1\), which means that \((a,b)\) is in the shaded area of Fig. 5, which we denote by \(\Omega\). Consider point \((a_{i},b_{i})\) in this area and the square \(X_{i}\) of size \(d_{i}\), whose right upper corner is \((a_{i},b_{i})\) (Fig. 5). Such a square is also denoted by \([a_{i},b_{i};d_{i}]\). Then for any triangle whose \((a_{i},b_{i})\)-values are within this square (some portion of it may be outside \(\Omega\)), its competitive ratio can be bounded by \(\frac{a_{i}}{a_{i}-d_{i}}f(\Delta(1,a_{i},b_{i}))\), which we call the competitive ratio of the square \(X_{i}\) and denote by \(g(X_{i})\) or \(g([a_{i},b_{i};d_{i}])\). Additionally, for \(i=0\) the value \(g(X_{0})\) is bounded by \(\frac{n_{0}}{n_{0}-2}C_{n_{0}}\). Consider a finite set of squares \(X_{0},X_{1},\ldots,X_{k}=[a_{k},b_{k};d_{k}],\ldots,X_{m}\) with the following properties (see also Fig. 5):  
1. The right-upper corners of all the squares are in \(\Omega\). 2. \(X_{0}\) is the rightmost square, which must be \([i,i+1;2]\) for some \(i\). 3. The area of \(\Omega\) between \(a=1\) and \(i\) must be covered by those squares, or any point \((a,b)\) in \(\Omega\) such that \(1\leq a\leq i\) must be in some square. Suppose that all the values of \(g(X_{i})\) for \(0\leq i\leq m\) are at most \(r_{0}\). Then one can easily see that the set \(S=\bigcup_{i=0,m}\left\{\Delta(1,a_{i},b_{i}),\Delta(1,a_{i}-d_{i},b_{i}-d_{i} )\right\}\) of triangles satisfies conditions (i) to (iii) given in Sec. 2, i.e., we have obtained the algorithm whose competitive ratio is at most \(r_{0}\). The issue is how to generate those squares efficiently. Note that \(g(X)\) decreases if the size \(d\) of the square \(X\) decreases. Specifically, we can subdivide each square into squares of smaller size to obtain an improved competitive ratio. However, it is not the best policy to subdivide all squares evenly since \(g(X)\) for a square \(X\) of the same size substantially differs in different positions within \(\Omega\). Note this phenomenon especially between positions close to the origin (i.e., both \(a\) and \(b\) are small) and those far from the origin (the former is larger). Thus our approach is to subdivide squares \(X\) dynamically, or to divide the one with the largest \(g(X)\) value in each step. Also observe that as squares move to the right in Fig. 5 then the \(g\) value decreases due to Lemma 1. Figure 5: Covering \(\Omega\)  
Figure 6: Division of a square  
We give now an informal description of the procedure for generating the squares, the formal description is given in Procedures 1 and 2. Broadly speaking one starts with square near the origin, then subdivides this square, and continues by creating a new square to the right. Due to Lemma 1 this process is bounded. The procedure begins with a single square \([2,3;2]\). Note that its \(g\)-value is poor (in fact, not bounded). Next, square \([2,3;2]\) is split into four squares of size 1 as shown in Fig. 6: \([1,3;1],[1,2;1],[2,2;1]\) and \([2,3;1]\). For each of these squares, the \(g\)-value is then calculated in the following way: If the square is of the form \([i,i+1;\ell]\) for some \(i,\ell\), the \(g\)-value can be calculated immediately by Lemma 1. Otherwise, we use the linear program described in [14] to determine the competitive ratio of triangle \(\Delta(1,a,b)\).