# Linking Off-Road Points to Routing Networks
## 3 Linkage to Network  
Let us again formulate our posed problem on a surface \(M\): Given a routing network \(G=(V,E,c,i,N)\in\mathcal{G}\), its geometric representation \(N\) and a lower-bounding metric \(d\), we want to add a new vertex \(v^{\prime}\
ot\in V\) to \(G\) in such a way that:  
* The resulting routing network stays valid. In particular, the graph shall remain connected, i.e., there is an edge with \(v^{\prime}\) as an end. * The modified geometric representation \(i^{\prime}\) maps \(i^{\prime}(v^{\prime})\) to \(M\). * \(i(v^{\prime})\in M\). Informally, this means that a pedestrian can access \(v^{\prime}\) from the ground. * \(d\) is still a valid lower-bounding metric. We call this transformation a _linkage_ and pose now a formal definition of it:  
**Definition 8**. : _Let \(G=(V,E,c,i,N)\in\mathcal{G}\) and \(\ell\) be the quasimetric induced by \(i\). \(A\) linkage is some mapping \(\sigma:M\times\mathcal{G}\to\mathcal{G}\) with the property that the resulting quasimetric network \(G^{\prime}:=(V^{\prime},E^{\prime},c^{\prime},i^{\prime},N^{\prime}):=\sigma (a,G)\) holds the conditions:_  
* \(i^{\prime}:E^{\prime}\cup V^{\prime}\to N^{\prime}\) _with_ \(i^{\prime}\mid_{V^{\prime}}=i\mid_{V}\) _and_ \(i^{\prime}\mid_{(E\cap E^{\prime})}=i\mid_{(E\cap E^{\prime})}\)_._
* \(V^{\prime}=V\cup\{v^{\prime}\}\) _with_ \(i^{\prime}(v^{\prime})=a\) _for some_ \(v^{\prime}\) _(that is not necessarily part of_ \(V\)_)._
* \(i^{\prime}(V^{\prime}\cup E^{\prime})\subset N^{\prime}\)_; hence,_ \(a\in N^{\prime}\cap M\)_._
* _There exist some_ \(x,y\in V\) _with_ \((v^{\prime},x)\in E^{\prime}\) _and_ \((y,v^{\prime})\in E^{\prime}\)_._
* \(c^{\prime}:E^{\prime}\to\mathbb{R}\) _with_ \(c^{\prime}\mid_{E\cap E^{\prime}}=c\)_._
* \(G^{\prime}\) _respects the metric_ \(d\)_._
* _Hence,_ \(\ell(x,y)=\ell^{\prime}(x,y)\) _for all vertices_ \(x,y\in V\) _where_ \(\ell\) _and_ \(\ell^{\prime}\) _are the quasimetrics induced by_ \(i\) _and_ \(i^{\prime}\)_, respectively._  
The crux of this problem lies in the construction of appropriate edges or vertices that sustain the properties of a routing network. In the following, we introduce some construction steps to elaborate a simple but complete solution in the end. First, we treat the special case that we want to add some point \(a\in M\cap N\) that belongs to \(G\), i.e., the location reference \(v\in V\) with \(i(v)=a\) already exists. Hence, nothing has to be done. Second, \(a\in M\cap N\) may be in the image \(i(e)\) of some edge \(e\in E\). Then, we split \(e\) into two pieces by linear interpolation and add the location reference of \(a\) as an intermediate piece. Formally, we have:  
**Example 3**. : _We define the linear interpolation \(G^{\prime}:=\sigma(a,G)\) of \(G:=(V,E,c,i)\in\mathcal{G}\) for a point \(a\in M\) as follows:_  
1. _If there exists some_ \(v\in V\) _such that_ \(i(v)=a\)_, then_ \(G^{\prime}:=G\)  
Figure 1: Curvature on an ellipsoid embedded in \(\mathbb{R}^{3}\). The ellipsoid’s surface is visualized in dashed green color. We take two points \(u\) and \(v\) on this ellipsoid. If we cut the ellipsoid along these two points, we obtain a circle on which both points lie. The arc (blue color) that connects both points is a geodesic \(g(u,v)\) of the surface [25]. A straight line (red color) would be shorter than the geodesic and hence the \(l^{2}\)-norm \(\|\cdot\|_{2}^{\mathbb{R}^{3}}\) is a lower bound. _._
2. _If there exists an edge_ \(e\in E\) _such that_ \(a\in i(e)\setminus i(V)\)_, then there is some_ \(\lambda\in(0,1)\) _such that_ \(\gamma_{e}(\lambda)=a\)_, where_ \(\gamma_{e}\) _is the line induced by_ \(i(e)\) _due to the line-string property. Let_ \(x,y\in V\) _be the vertices connected by_ \(e\) _such that_ \(e=(x,y)\)_. We add a new vertex_ \(v^{\prime}\
ot\in V\) _with_ \(i(v^{\prime})=a\)_.