Round-trip nearest neighbors on road networks for location based services
Debajyoti Ghosh, Prosenjit Gupta · 2016
Location Based Services integrate the knowledge of the geographical location of a mobile device with other information to provide various services. Successful provisioning of LBS systems had been hindered in the past by various infrastructure constraints. However progress on various fronts in the last few years coupled with increased usage of mobile devices have resulted in increased interest in LBS applications. Queries on road networks form an important class of problems in LBS. We consider a new pragmatic variant of the nearest neighbor problem defined in terms of a round-trip distance function on road networks where due to presence of one-way roads and asymmetric exits, the distance function is not symmetric. In this paper, we prove several properties of the round trip nearest neighbor of a query point and propose an efficient algorithm for reporting the same.