# Linking Off-Road Points to Routing Networks
## 1 Introduction
### Related Work  
Spatial reasoning can be conducted on graph-theoretical foundations only if all interesting points are represented by the graph. Moreover, a connected graph is necessary for useful routing queries. In most common techniques, missing parts of the street infrastructure are either:  
1. Extracted from digital imagery;
2. Collected by sensors (e.g., GPS-enabled tracking devices);
3. Created manually.  
Every case may lead to an inaccurate or incomplete routing network. If the position is uncertain or the information about the area is incomplete, it is not possible to exactly match a location point with a vertex on a routing network. In scenario (1), the capturedimages can be used to reverify the constructed routing network. [PERSON] and [PERSON]'s algorithm [8] uses detour lengths and connection completeness as criteria when analyzing imagery. In terms of case (2), this problem is common for navigation systems that have to figure out on which path an object is moving by analyzing its trajectory. In fact, this process is so frequent that it has a name of its own--the _map matching problem_[9]. For instance, [PERSON] and [PERSON] [10] used collected trajectories to discover missing road parts. Alternatively, [PERSON] et al. [11] took an initial candidate list and use transition probability to minimize the error of choosing the right trajectory. For case (3), we have in general no additional information to ensure our decision for linking a non-mapped point to the network. The easiest setting is a planar routing network mapped on a surface: For each point of interest (POI) we want to connect, we just add an edge to the closest location of the graph. For proximity analysis, [PERSON] and [PERSON] [12] connected each geolocation with the nearest reference point of the routing network. [PERSON] and [PERSON] [13] took the Delaunay triangulation of their existing road network as a criterion for linking non-connected points. They further discarded those parts of the Delaunay graph that intersected with obstacles. Last but not least, [PERSON] et al. [14] emphasized possible detours when propagating their method to link new points to the network. They called the newly created edge a _feed-link_. [PERSON] and [PERSON] [15] further proposed an algorithm to compute this feed-link in linear time.  
For mobile ad hoc networks, [PERSON] et al. [16] proposed so-called _terminode_ routing to address holes in mobile network topologies. [PERSON] et al. [17] reviewed various geometric routing strategies for wireless network protocols.  
Although some of these approaches share similarities with the techniques introduced in this article, they differ in the problem statement. In fact, to the best of our knowledge, we are unaware of any former study adding points to spatial systems based on geometric distances. Our problem setting has not been treated in terms of spatial databases that may store wide routing networks along with spatial representations of both the routing networks' vertices and POIs. We provide in this paper a conceptional foundation for describing routing networks globally on Earth's surface that is then translated to the field of spatial databases.