# Linking Off-Road Points to Routing Networks
## 2 Preliminaries
### Graphs  
In order to represent a routing network on the Earth, let us recall the definition of a graph [18]:  
**Definition 1**. : _A directed weighted graph \(G:=(V,E,c)\) is a triple consisting of a vertex set \(V\), an edge set \(E\subseteq V\times V\) and a cost measure \(c:E\to[0,\infty)\). Let us denote for two vertices \(v_{1},v_{2}\in V\) with \((v_{1},v_{2})\in E\) the edge that connects \(v_{1}\) to \(v_{2}\). To avoid the excessive usage of brackets, we simplify the expression \(c((u,v))\) to \(c(u,v)\) for an edge \((u,v)\in E\). A walk \(P:=(v_{1},\ldots,v_{n})\) is a consecutive succession of vertices for an arbitrary \(n\in\mathbb{N}\) such that there exists an edge \((v_{i},v_{i+1})\in E\) for each \(i\in\{1,\ldots,n-1\}\). If the vertices \(v_{i}\) and \(v_{j}\) of a walk \(P:=(v_{1},\ldots,v_{n})\) are pairwise different for all \(i\
eq j\), we call \(P\) a path. We say the walk \(P\) with \(n\in\mathbb{N}\) vertices follows \"from \(a\in V\) to \(b\in V\)\" when \(v_{1}=a\) and \(v_{n}=b\). We call \(G\) connected if there exists a walk from \(a\) to \(b\) for all \(a,b\in V\). Moreover, we define the length of the walk \(P=(v_{1},\ldots,v_{n})\) by \(\ell(P):=\sum_{i=1}^{n-1}c(v_{i},v_{i+1})\). Further, we denote with \(\ell(a,b)\) the infimum of the lengths of all walks from a to \(b\), i.e.,_  
\[\ell(a,b):=\inf\{\ell(P):P\text{ walk from a to }b\}.\]  
We further want to examine a special class of graphs whose path length function \(\ell\) is restricted in such a way that we can find a metric that is a lower bound of \(\ell\). This restricts \(\ell\) to be member of the following function class:  
**Definition 2**. : _Let \(V\) be a set. A mapping \(\ell:V\times V\to\mathbb{R}\) is called a quasimetric if it is a metric which does not need to fulfill the symmetry property._  
**Remark 2**. : _For our approach, we neglect a possible symmetry property of routing networks. In fact, cost functions based on fuel or calorie consumption and estimated time are valid examples for directed networks that are in general non-symmetric._  
**Definition 3**. : _If \(E\
eq\emptyset\) and \(c\) of a connected graph \(G:=(V,E,c)\) supports the conditions_  
\[(v,v) \in E\text{ for each }v\in V\] _(reflexivity),_ \[c(u,v) =0\text{ if and only if }u=v\] _(definiteness),_  
_then \(\ell:V\times V\to\mathbb{R}\) is a quasimetric. We then call \(G\) a quasimetric network and \(\ell\) the quasimetric induced by \(c\)._  
See [19] for an indexing data structure built on a quasimetric network. **Lemma 1**. : \(\ell\) _respects the triangle inequality, although \(c\) is not required to hold this property._  
Proof. : Because \(c(e)\geq 0\) for all \(e\in E\), a shortest walk will always be a simple path: Every walk that contains a circle is not a path. It can be made simple by removing all circles. However, this will also shorten the length of the walk. Hence, the definition of \(\ell\) stays the same when taking the infimum of the length of all paths. We will call a walk that meets this condition a _shortest path_. Hence, we yield:  
* From \(\ell(P)\geq 0\)\(\forall P\), we obtain the non-negativity of \(\ell\). * As \(\ell(P)>0\) for all walks from \(u\) to \(v\in V\), \(u\
eq v\), we obtain by definition \(\ell(u,v)>0\) for all \(u,v\in V,u\
eq v\). As \(c(v,v)=0\) for each \(v\in V\), we can conclude that \(\ell((v,v))=0\) for each \(v\in V\). Thus, we yield the positive definiteness of \(\ell\). * If we define the concatenation of walks by \((v_{1},\ldots,v_{n})\circ(w_{1},\ldots,w_{n}):=\) \[\left\{ \begin{aligned} &(v_{1},\ldots,v_{n},w_{2},\ldots,w_{n})& \text{if }v_{n}=w_{1},\\ &\text{undefined}&\text{otherwise},\end{aligned} \right.\]  
the triangle inequality is simple to show: For arbitrary \(u,v,w\in V\), let \(P_{uv}\) be a path from \(u\) to \(v\) and \(P_{vw}\) a path from \(v\) to \(w\). Then, we can generate a walk \(P_{uv}:=P_{uv}\circ P_{vw}\) by combining both paths, so we have \(\ell(P_{uw})=\ell(P_{vw})+\ell(P_{uv})\).