# Linking Off-Road Points to Routing Networks
## 3 Linkage to Network
Let us set_ \(c^{\prime}(x,v^{\prime}):=\lambda c(x,y)\) _and_ \(c^{\prime}(v^{\prime},y):=(1-\lambda)c(x,y)\)_. If_ \((y,x)\in E\)_, we further set, due to_ \(\text{Im }\gamma_{(x,y)}=\text{Im }\gamma_{(y,x)}\)_,_ \(c^{\prime}(v^{\prime},x):=\overleftarrow{\lambda}c(y,x)\) _and_ \(c^{\prime}(y,v^{\prime}):=(1-\overleftarrow{\lambda})c(y,x)\) _with_ \(\overleftarrow{\lambda}\in(0,1)\) _such that_ \(\gamma_{(y,x)}(\overleftarrow{\lambda})=a\)_. In the end, we define_ \(E^{\prime}\) _as the set_ \(E\) _without_ \(\{(x,y),(y,x)\}\)_, but with the new edges used above -_ \(\{(x,v^{\prime}),(v^{\prime},y)\}\)_, and_ \(\{(v^{\prime},x),(y,v^{\prime})\}\) _if_ \((y,x)\in E\)_._ _Let_ \(\ell\) _and_ \(\ell^{\prime}\) _be the quasimetrics that are induced by_ \(c\) _and_ \(c^{\prime}\)_, respectively. Then,_ \(\ell^{\prime}\mid_{V\times V}=\ell\) _holds due to_ \(\ell(x,y)=c(x,y)=c^{\prime}(x,v^{\prime})+c^{\prime}(v^{\prime},y)=\ell^{ \prime}(x,y)\)_. Thus, we yield the_ _beeline property with_ \(i^{\prime}(x,v^{\prime})=\gamma_{c}([0,\lambda]),i^{\prime}(v^{\prime},y)=\gamma _{c}([\lambda,1])\)_. With the same arguments, we are able to preserve the properties of a routing network for_ \((y,x)\)_, if_ \((y,x)\in E\)_. Because we have not changed the image of_ \(i\)_, we can just set_ \(N^{\prime}:=N\) _and hence we are finished._
3. _Otherwise, we are certain that_ \(a\
ot\in N\)_. We use a not yet defined method to create a new network_ \(G^{\prime}=(V^{\prime},E^{\prime},c^{\prime},i^{\prime},N^{\prime})\) _with some_ \(E^{\prime}\)_,_ \(c^{\prime}\) _and_ \(N^{\prime}\)_._ _In both specified cases, the linear interpolation is a linkage, i.e.,_ \(\sigma(G):=(V^{\prime},E^{\prime},c^{\prime},i^{\prime},N)\) _fulfills the properties of Definition_ 8_. See Figure_ 2 _for an illustration._  
Note that Example 3 takes care just for points that are already part of \(N\). In the following, we try to fill case (3). Here, we can be sure that the point \(a\in M\) to add does not belong to the image of \(i\); hence, \(a\
ot\in N\). In order to keep the graph connected, we have to add some edges after inserting the location reference of \(a\). For the search of suitable access points, we take only those segments of the routing network into account that intersect with the manifold \(M\). Informally, the intersection takes account for accessibility from the ground. For example, we consider the internal segments of a tunnel (\"below \(M\)\") or bridge (\"above \(M\)\") inaccessible. To access a tunnel or bridge, a path to the entrance of a tunnel or the vertex that connects the bridge with \(M\) has to be found. For a query point \(a\in\varphi_{j}V_{j}\), if the routing network can be drawn on the surface, i.e., the condition \(\pi_{V_{j}}N=N\cap V_{j}\) holds, then we do not have to care about inaccessible points. The first example tries to solve the problem by simply adding an edge to the closest accessible vertex of the routing network, see Figure 3 for an example. Unfortunately, the resulting graph may not be a routing network anymore. Nevertheless, we can use this approach to elaborate upon Example 4. Figure 3: Vertex linkage. We link a point \(a\) to the node \(i(x)\) of the routing network. Figure 2: Linking a point \(a\) by linear interpolation of an edge \(e\). **Counter-Example 1**. : _We define the vertex linkage \(G^{\prime}:=\sigma(a,G)\) of \(G:=(V,E,c,i,N)\in\mathcal{G}\) for a point \(a\in M\) that is based on linear interpolation. Case (3) of Example 3 is implemented as follows: Define \(V^{\prime}:=V\cup\{v^{\prime}\}\) with some \(v^{\prime}\
ot\in V\), and set \(i^{\prime}(v^{\prime}):=a\) and \(i^{\prime}\mid_{V}=i\) otherwise. Further, let \(u:=\operatorname*{argmin}_{v\in V:i(v)\in M}d(i(v),a)\). We then define \(E^{\prime}:=E\cup\{(u,v^{\prime}),(v^{\prime},u)\}\) with \(c^{\prime}(u,v^{\prime})=c^{\prime}(v^{\prime},u)=d(a,i(u))\). In general, \(\sigma(G):=(V^{\prime},E^{\prime},c^{\prime},i^{\prime},N\cup i^{\prime}(u,v^ {\prime}))\) is not a valid linkage with regards to Definition 8.