## 2 Methods
### Phase 1
#### 2.1.2 Procedure for the Construction of the Girding Polygon
\begin{table}
\begin{tabular}{c l} \hline \hline
**PROCEDURE**_polygon_(\(V\), \(v^{1}\), \(v^{2}\), \(v^{3}\), \(v^{4}\) ) \\ \hline
1 & \(P:=(v^{1})\) \\
2 & \(k:=v^{1}\) \\
3 & **WHILE**\(k\
eq v^{2}\)**DO** \\
4 & form a subset of vertices \(V^{*}:=\{\,i\mid x_{i}<x_{k}\,\,\wedge\,y_{i}\geq y_{i^{2}}\,;\,i\in V\}\) \\
5 & form a subset of edges \(E^{*}:=\{(k,j);i\in V^{*}\}\) \\
6 & form a set of angles \(\Theta^{*}:=\{\theta(k,j);(k,j)\in E^{*}\}\) \\
7 & get the minimum angle \(\theta(k,l)\) from \(\Theta^{*}\) \\
8 & append the vertex \(l\) to \(P\) and update \(k\) equal to \(l\). \\
9 & **WHILE**\(k\
eq v^{3}\)**DO** \\
10 & form a subset of vertices \(V^{*}:=\{\,i\mid x_{i}\leq x_{v^{3}}\,\,\wedge\,y_{i}<y_{k}\,;\,i\in V\}\) \\
12 & form a subset of edges \(E^{*}:=\{(k,j);i\in V^{*}\}\) \\
13 & form a set of angles \(\Theta^{*}:=\{\theta(k,j);(k,j)\in E^{*}\}\) \\
14 & get the minimum angle \(\theta(k,l)\) from \(\Theta^{*}\) \\
15 & append the vertex \(l\) to \(P\) and update \(k\) equal to \(l\). \\
16 & **WHILE**\(k\
eq v^{4}\)**DO** \\
17 & form a subset of vertices \(V^{*}:=\{\,i\mid x_{i}>x_{k}\,\,\wedge\,y_{i}\leq y_{i^{4}}\,;\,i\in V\}\) \\
18 & form a subset of edges \(E^{*}:=\{(k,j);i\in V^{*}\}\) \\
20 & form a set of angles \(\Theta^{*}:=\{\theta(k,j);(k,j)\in E^{*}\}\) \\
21 & get the minimum angle \(\theta(k,l)\) from \(\Theta^{*}\) \\
22 & append the vertex \(l\) to \(P\) and update \(k\) equal to \(l\). \\
23 & **WHILE**\(k\
eq v^{1}\)**DO** \\
24 & form a subset of vertices \(V^{*}:=\{\,i\mid x_{i}\geq x_{v^{1}}\,\,\wedge\,y_{i}>y_{k}\,;\,i\in V\}\) \\
25 & form a subset of vertices \(E^{*}:=\{(k,j);j\in V^{*}\}\) \\
26 & form a set of angles \(\Theta^{*}:=\{\theta(k,j);(k,j)\in E^{*}\}\) \\
27 & get the minimum angle \(\theta(k,l)\) from \(\Theta^{*}\) \\
28 & append the vertex \(l\) to \(P\) and update \(k\) equal to \(l\). \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Procedure _polygon_. Figure 2: Angle \(\theta(i,j)\). set of \(n-1\) edges \(E^{*}\) is formed in time \(\{f(n)=n-1\}\). In lines 6, 13, 20, and 27, the set of angles \(\Theta^{*}\) consisting of at most \(n-1\) elements is formed in time \(\{f(n)=n-1\}\). In lines 7, 14, 21, and 28 to find the minimum angle in set \(\Theta^{*}\) at most \(n-1\) comparisons are needed and the lemma follows. In Figure 3, we illustrate an example with \(V=\{1,2,\cdots,6\}\) with coordinates \(X=\{x_{1},x_{2},\cdots,x_{6}\}\) and \(Y=\{y_{1},y_{2},\cdots,y_{6}\}\). The extreme points are: \(v^{1}=4\), \(v^{2}=2\), \(v^{3}=5\) and \(v^{4}=5\) and \(P=(4,2,5,4)\). Initially, \(P=(4)\). Then, vertex 2 is added to polygon in Step 1, vertex 5 is added in Step 2; Step 3 is not carried out because \(v^{3}=v^{4}\); vertex 4 is added at Step 4. Using polygon \(P(V)\) constructed by the Procedure Polygon, we obtain our initial, yet infeasible (partial) tour \(T_{0}=(t_{1},t_{2},\cdots,t_{m},t_{1})\) that is merely formed by all the points \(t_{1},t_{2},\cdots,t_{m}\) of that polygon, where \(t_{1}=v^{1}\) and \(m\) is the number of the points. In the example of Figure 3, \(P\) is the initial infeasible tour \(T_{0}=(4,2,5,4)\). \(V\setminus T_{0}=\{1,3,6\}\) is the set of points that will be inserted into the final tour.