# An Effective Algorithm for Finding Shortest Paths in Tubular Spaces
## 5 Computational Results
### Computation Time  
We firstly implemented them considering a tube with the centerline in 3D space consisting of a 4 cm straight length and two curved segments belonging to two perpendicular planes. The radii of both curves are 12 cm and their lengths are 16 cm and 20 cm, respectively, as detailed in Figure 10. The inner diameter of the tube is 3 cm. We chose the discretization step \(h=2\) mm (\(N=199\)). Each meshed disk is made by dividing the  
Figure 9: The oriented drilling process : (1) \(\mathbf{C}_{i-1}\) can see \(\mathbf{T}\) in section \(S_{j}\), (2) expand the examined direction in the vicinity of \(\mathbf{T}\) until seeing \(\mathbf{T}_{new}\) in section \(S_{k}(k>j)\), (3) update \(\mathbf{T}\) by \(\mathbf{T}_{new}\), \(S_{j}\) by \(S_{k}\) and repeat step 2 for the new \(\mathbf{T}\) and \(S_{j}\), (4) repeat step 3, (5) the expanding process is over and we do not find any farther section \(S_{k}=\emptyset\), and we then compare all the length of sight passing through the visible area in \(S_{j}\) to obtain the direction corresponding to the longest length of sight, and (6) initialize the next correct point of the shortest path \(\mathbf{C}_{i}\) as the intersection point between the correct direction and cross-section \(S_{i}\).  
cross-section into 25 concentric circles (\(N_{\rho}=25\)) whose circumference is divided into four equal arcs (\(N_{\theta}=4\)).  
As shown in Figure 10, the proposed method enables obtaining a shorter and smoother solution than [PERSON]'s method with the same mesh (a detailed analysis will be provided in the next sub-section). Another advantage of the proposed algorithm compared to [PERSON]'s method is the computation speed as a large number of unimportant vertices and arcs can be ignored in the process (see Figure 10). As the time complexity of the proposed method has a huge variation depending on the specific shape of the tubular space, the computation time (instead of the theoretical time complexity) will be considered for the comparison result. Table 1 shows how the computation times of the two methods depend on the number of nodes in the meshed circular disks. As we can see, the computation time of [PERSON]'s method will increase by a factor of 4 if \(M\) is doubled (\(M\) is the number of nodes in a meshed disk). This is consistent with the time complexity \(O(|A|)\) of [PERSON]'s algorithm (\(|A|=2M+(N-1)M^{2}\)). For the proposed method, this increasing rate is less than two.  
\begin{table}
\begin{tabular}{c c c} \hline \hline \multirow{2}{*}{\(M=100\)} & \multicolumn{2}{c}{\(N_{\rho}=25\), \(N_{\theta}=4\)} \\  & T.P = 0.76, T.D = 4.10 \\ \hline \multirow{2}{*}{\(M=200\)} & \(N_{\rho}=50\), \(N_{\theta}=4\) & \(N_{\rho}=25\), \(N_{\theta}=8\) \\  & T.P = 0.96, T.D = 16.66 & T.P = 1.05, T.D = 15.77 \\ \hline \multirow{2}{*}{\(M=400\)} & \(N_{\rho}=100\), \(N_{\theta}=4\) & \(N_{\rho}=25\), \(N_{\theta}=16\) \\  & T.P = 1.63, T.D = 64.67 & T.P = 1.51, T.D = 60.19 \\ \hline \multirow{2}{*}{\(M=800\)} & \(N_{\rho}=200\), \(N_{\theta}=4\) & \(N_{\rho}=25\), \(N_{\theta}=32\) \\  & T.P = 3.03, T.D = 259.23 & T.P = 2.01, T.D = 219.82 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Comparison result in computation time of the two methods with different meshes.  
Figure 10: Tubular space with two curved segments in space. By **L.P**, and **T.P**, we denote the path length and the computation time for the solution obtained by the proposed method. Similarly, **L.D**, and **T.D** for [PERSON]’s algorithm. The exact solution is determined by using [PERSON]’s method with \(N_{\rho}=144\) and \(N_{\theta}=64\).