# An Effective Algorithm for Finding Shortest Paths in Tubular Spaces
## 4 The ESP Searching Algorithm Based on Visibility
### Geometric Properties of the ESP in Tubular Space  
Definition 3: For every point \(\textbf{X}\in S_{i}\subset\Omega\), \(i\
eq N+1\), the cross-section \(S_{i}\) divides \(\Omega\) into two sub-spaces, and a direction from **X** is said to be positive (+) if it is towards the sub-space containing the destination. According to Definition 3, any point in \(\Omega\) (not belonging to \(S_{N+1}\)) will have an infinite number of positive directions (see Figure 3). Obviously, during the movement, the correct direction of the particle is always a positive direction. Definition 4: Two points **X**, \(\textbf{Y}\in\Omega\) are said to see each other if the line segment joining them \(\overline{\textbf{X}\textbf{Y}}\) is totally contained by \(\Omega\). Definition 5: A cross-section \(S\subset\Omega\) is visible from a point \(\textbf{X}\in\Omega\) if there exists a point \(\textbf{Y}\in S\) that can be seen by **X**. Lemma 2: If a point **X** inside the tube can see a cross-section \(S\) of the tube, the area part in \(S\) that can be seen by **X** must be a convex set (as illustrated in Figure 4). The proof of this lemma is detailed in Appendix A.1. Definition 6: From a point **X**\(\in\Omega\), the \"**length of sight**\" corresponding to a positive direction is the distance between **X** and the farthest point in \(\partial\Omega\) that can be seen by **X** along the positive direction. The line segment corresponding to this length is called the **line of sight**. We then have the geometric structure of the shortest path between two points (which are not in each other's line of sight) in a tubular space. Theorem 1: By **f**, we denote the shortest path between two arbitrary points **X** and **Y** inside the tubular space \(\Omega\). If **X** cannot see **Y**, then there exist curved parts of **f** lying on the inner lateral wall of the tube \(\partial\Omega\). Outside these parts, **f** consists of a union of straight line segments which are tangent to the boundary surface \(\partial\Omega\). Figure 4: The visible area of a cross-section \(S_{i}\) is described by the yellow zone(s) which must be unique and continuous. Figure 3: (**Left**) The dashed red rays describe the positive directions. (**Right**) **A** can see **B** and **D** because the line segments \(\overline{\textbf{A}\textbf{B}}\) and \(\overline{\textbf{A}\textbf{D}}\) are totally contained by \(\Omega\). Furthermore, by this definition, **A** cannot see **C**. The green and blue dashed lines terminating at the boundary \(\partial\Omega\) illustrate the line of sights. Among them, the blue one is the longest length of sight, an important concept used in the following method. **Theorem 2**. : _The curved parts of \(\mathbf{f}\) are geodesic paths on \(\partial\Omega\). Moreover, they are on the surface of the negative curvature._  
Proof. : The proof of Theorem 1 was presented in [29]. To prove Theorem 2, we employed Lemma 1. As the curved parts of \(\mathbf{f}\) are also the shortest paths connecting their ends, they must be geodesic paths on the boundary surface \(\partial\Omega\)[37]. Moreover, if a curved path of \(\mathbf{f}\) exists that is outside the surface of the negative curvature, we always find on this path two neighboring points that can see each other (see Figure 5). As the straight line segment joining these points is shorter than the geodesic path between them, then \(\mathbf{f}\) is not the shortest one connecting \(\mathbf{X}\) and \(\mathbf{Y}\). This contradicts the definition of \(\mathbf{f}\) (Q.E.D.). These two theorems lead us to two important corollaries. **Corollary 1**. : _Let \(\mathbf{X}\) be a point on the ESP \(\mathbf{p}(s)\) that can see a point \(\mathbf{Y}\) so that the ray \(\mathbf{X}\mathbf{Y}\) is not the direction \(\mathbf{p}(s_{X})\) of the ESP at \(\mathbf{X}\). Let \((\alpha)\) be an arbitrary plane containing \(\mathbf{X}\mathbf{Y}\).