Path Queries and Data Collection in Geometric Networks

The shortest path problem is one of the most fundamental and well-studied problems in graph theory. Numerous real-world applications have stimulated research investigations for more than 50 years. Finding routes in road networks is a classical application motivating the study of the shortest path problem. The aim of this book is to provide means to efficiently compute a minimum cost path in different types of problem settings. We consider three different settings, all with an underlying metric space: transportation networks, anisotropic media and wireless sensor networks. The first part of the book focuses on the construction of a data structure that allows for efficient approximate quickest path cost queries in a transportation network. In the second part of the book, we study the minimum cost path problem in an environment in which the cost is direction dependent (anisotropic). We present an approximation algorithm to find a minimum cost path for a point robot moving in a planar subdivision, in which each face is assigned a translational flow that reflects the cost of travelling within this face. The final part is about Wireless Sensor Networks with Mobile Elements (WSNME).