# Linking Off-Road Points to Routing Networks
## 2 Preliminaries
### Routing Networks  
We now introduce another manifold \(N\) that accounts for routing networks. In general, we will allow \(N\
ot\subset M\), i.e., bridges, tunnels or other partially inaccessible street segments can be expressed by this model.  
**Definition 5**.: _Let \((V,E,c)\) be a quasimetric network. Further, let \(i:V\hookrightarrow N,E\to\mathbb{P}(N)\) be an embedding in a manifold \(N\subset\mathbb{R}^{3}\), where \(\mathbb{P}(N)\) is the power set of \(N\). Let the following conditions hold:_  
* \(i\mid_{V}:V\hookrightarrow N\subset\mathbb{R}^{3}\) _with_ \(\bigcup_{e\in E}i(e)=N\)_;_
* _For each_ \(n\in N\)_, there exists an_ \(m\in M\) _and an_ \(h\in\mathbb{R}\) _such that_ \(m+h\
u(m)=n\) _(embedding property). This property is based on the fact that street segments may not be on the surface. Informally, the parameter_ \(h\) _counts for the altitude difference between the ground and street; e.g., bridges have positive heights and tunnels negative heights. This separation between spherical data and altitude is also common when dealing with the WGS84 format that encodes points on_ \(M\) _by latitude and longitude_ _[_22_]__._
* _Let_ \(\pi_{M}\circ i:V\to M\) _be the (canonical) projection of the graph onto_ \(M\)_. Then, we assume that for all_ \(e\in E\) _there exists some_ \(j\in J\) _with_ \(\pi_{M}\circ i(e)\subset V_{j}\)_, i.e., we stipulate that the complete image of each edge is contained in at least one chart's image (containment property)._
* _For each edge_ \(e=(a,b)\in E\)_, there is a line_ \(\gamma_{e}:[0,1]\to N\) _with_ \(\gamma_{e}(0)=i(a),\gamma_{e}(1)=i(b)\)_, and_ \(i(e)=Im\ \gamma_{e}\)_, i.e.,_ \(\gamma_{e}\) _is a linear continuous, parameterized, geodesic line with_ \(a\) _and_ \(b\) _as endpoints (line-string property)._* _Two of these lines_ \(\gamma_{1}\) _and_ \(\gamma_{2}\) _are called equivalent when_ \(\gamma_{1}=\gamma_{2}\) _or_ \(\gamma_{1}(1-\cdot)=\gamma_{2}\)_. If we denote equivalence with_ \(\sim\) _and define the quotient set_ \(\Gamma:=\left\{\gamma_{e}:e\in E\right\}/\sim\)_, then_ \(\{\gamma(0,1):\gamma\in\Gamma\}\) _shall be a disjoint partition of_ \(N\setminus i(V)\) _(disjoint property)._ _We then call the tuple_ \(G=(V,E,c,i,N)\) \(a\) routing network_._ \(i(V)\subset N\)_, since_ \(G\) _is connected. In particular, if there exists an injection_ \(N\hookrightarrow V_{j}\subset\mathbb{R}^{2}\) _for some_ \(j\in J\)_, then the routing network_ \(G\) _is planar. Let us use the symbol_ \(\mathcal{G}\) _for the class of routing networks._  
**Remark 4**.: _The equivalence relation \(\Gamma\) can be understood as a lift of an equivalence relation that renders a directed graph undirected by_  
\[E/\sim\ :=\{\{u,v\}\ :\ (u,v)\in E\text{ or }(v,u)\in E\}.\]  
Let us consider the scenario of a spatial recommender system that uses the current location of a user to search for close POIs. The geolocation is collected by a mobile navigation system. Hence, the recommender has to map this polled location to its routing network in order to compute distances. The query point might not even be in the image of \(i\). We have to add these points to the graph by enhancing the number of vertices and edges in such a way that these particular points can be accessed by our network, as well. A vertex on which a geographic point is mapped is called a _location reference_. We will show some ideas on how to model location references so that shortest path evaluation should retrieve good results in relation to real-world expectation.