# Linking Off-Road Points to Routing Networks
## 3 Linkage to Network
The problem arises when there exists an edge \(e\in E\) with \(i(e)\cap i(u,v^{\prime})\
ot=\emptyset\). This is possible because there might exist an edge \(e=:(x,y)\) with the following properties (cf. Figure 4):  
* \(d(i(e),a)<d(i(u),a)\) and hence \(d(i(e),a)\leq\min\{d(i(x),a),d(i(y),a)\}\);
* There exist \(\alpha<0,w\in\gamma_{e}^{\perp}(0)\) and \(\lambda,\mu\in[0,1]\) such that \[\gamma_{e}(\lambda)+w=i(v)\text{ and }\gamma_{e}(\mu)+\alpha w=a,\] where \(\gamma_{e}\) is the geodesic of \(e\) induced by \(i\). Instead of the closest vertex, we can also take some route segment as an access point; we split an edge like the linear interpolation of Example 3 in such a way that the intermediate piece \(\tilde{v}\) acts as the new reference location. The image \(i(e)\) of a suitable edge \(e\) should have a point \(b=i^{\prime}(\delta)\in i(e)\cap M\) that is close to \(a\). On a plane \(\varphi_{i}V_{j}\) with \(\pi_{V_{j}}N=N\cap V_{j}\), the point \(b\) is determined by the perpendicular from \(a\) to the closest edge with respect to \(a\). In the general case, we have to follow the shortest geodesic from \(a\) to the routing network. This approach is visualized in Figure 5.  
**Example 4** (Edge Linkage). : _We define the edge 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 and implement the last procedure as follows: First, search for an_  
\[e:=\operatorname*{argmin}_{e\in E}d(i(e)\cap M,a)\]  
_and set \(\lambda:=\operatorname*{argmin}_{\lambda\in[0,1]}d(\gamma_{e}(\lambda),a)\), where \(\gamma_{e}\) is the geodesic line induced by \(i(e)\). Let \(x,y\in V\) be the vertices attached by \(e\) such that \(e=(x,y)\) and \(\delta:=d(\gamma_{e}(\lambda),a)\). There are now two cases to consider:_  
Figure 4: Vertex linkage creating a new edge intersecting with \(e\). After this operation, the graph is no longer planar, a setting we want to avoid. Figure 5: Edge Linkage. We link a point \(a\) to a newly created node \(b\) splitting the former edge \(e\) of the routing network. 1. \(\lambda=0\) or \(\lambda=1\), i.e., \(d(i(e),a)=d(i(x),a)\) or \(d(i(e),a)=d(i(y),a)\). Without loss of generality, let the equation \(d(i(e),a)=d(x,a)\) hold. Now we can apply a vertex linkage on \(G\) by Counter-Example 1 (setting \(u\gets x\)). This linkage holds the disjoint property. 2. Otherwise, \(\lambda\in(0,1)\). Hence, there exists some \(b\in N\) with \(b\in i(e)\) and \(d(i(e),a)=d(b,a)\). We apply linear interpolation on \(G\) with \(b\) and yield a new network \(\sigma(b,G)=:\tilde{G}:=(\tilde{V},\tilde{E},\tilde{c},\tilde{i},N)\) with \(\tilde{i}(\tilde{v})=b\) for some \(\tilde{v}\in\tilde{V}\). Note that the rule applied by linear interpolation will not modify \(N\). If we exchange \(G\) with \(\tilde{G}\), the first case holds, since there exists an edge \(\tilde{e}:=\operatorname*{argmin}_{\tilde{v}\in E}d(\tilde{i}(\tilde{v}),a)\) with \(\min_{\lambda\in[0,1]}d(\gamma_{e}(\tilde{\lambda}),a)\in\{0,1\}\). Proof. : For (2), we need to show that there is no \(e^{\prime}\in E^{\prime}\) that intersects with \(E^{\prime}\setminus\{e^{\prime}\}\). Let us assume that such an \(e^{\prime}\in E^{\prime}\) exists. As we have merely exchanged \(e\) with \(\{(x,v),(v,y)\}\) in \(E\), \(e^{\prime}\) has to intersect either \((x,v^{\prime})\) or \((v^{\prime},y)\).Then, \(d(i(e^{\prime}),a)<\min\{d(i(x,v^{\prime}),a),d(i(v^{\prime},y),a)\}\)\(=\)\(d(i(e),a)\), a contradiction to the selection of \(e=(x,y)\) to be the closest edge to \(a\). Retrieving the closest edge/vertex is usually conducted by a nearest-neighbor search on the database index. A common spatial index structure is the R-tree [26] that builds bounding boxes of geometries. For instance, [PERSON] et al. [27] elaborated upon a branch-and-bound algorithm that evaluates distances between bounding boxes. When used in real-world scenarios, it is often the case that some point \(a\in M\) is very close to a mapped vertex, but the coordinates do not match exactly.