We consider the problem of quickly providing strong lower bounds for the planar Euclidean shortest path (ESP) problem. Such lower bounds are crucial for guiding the search in A* type approaches or for proving quality guarantees for algorithms that compute approximate solutions. Our contributions are two-fold: we show how to simplify ESP instances such that computing and storing a visibility graph becomes feasible while distances within the simplified instance are guaranteed to constitute lower bounds for the original problem instance. Furthermore we show how to precompute a space efficient data structure that allows to perform distance queries on visibility graphs within few microseconds with negligible space overhead.

The radius of a graph is an important structural parameter which plays a key role in social network analysis and related applications. It measures the minimum shortest path distance that is required to reach all nodes in the graph from a single node. A node from which all other nodes are within a distance equal to the radius is called a center of the graph. In a graph with n nodes and m edges, the center and the radius can be determined in Õ(nm) by computing shortest path distances between all pairs of nodes. Fine-grained complexity results suggest that asymptotically faster algorithms are unlikely to exist. In this paper, we describe a novel randomized algorithm for exact radius computation in weighted digraphs with an expected running time in Õ(d³m) where d is the so-called combinatorial dimension. Our methodology is inspired by Clarkson’s algorithm for LP-type problems. The value of d denotes the size of a basis, which is a smallest subset of nodes which enforce the same radius as the whole node set. While we show that there exist graphs with d ∈ Θ(n), our empirical analysis reveals that even large real-world graphs have small combinatorial dimension. This allows us to compute the radius in near-linear time on such instances. The significantly improved scalability can be clearly observed in our experimental evaluation on a diverse set of benchmark graphs.

We revisit an interesting route planning problem introduced by Reza, Ali and Cheema [15] that we call the Bus Stop Problem (BSP). Given a road network and a set of agents with individual start and goal positions, find an appropriate start and stop position for a bus such that the agents reach their goals as fast as possible (by taking the bus). We show how this problem can be solved optimally by a modification of Dijkstra's algorithm, substantially improving and simplifying the approaches suggested in [15]. Furthermore, we consider multiple objective functions and discuss a natural generalization of the BSP that can be solved efficiently as well.

Contraction Hierarchies (CH) are one of the most popular techniques for accelerating shortest path queries. In previous works, it has been shown that CH in principle can be instrumented to also produce variable level-of-detail renderings of road networks. Yet, the existing approach still suffers from severe drawbacks like topological inconsistencies or distortion of the overall shape of the road network, which impairs the practical usability. We significantly improve upon the existing approach both in terms of quality of the visual representation as well as query times. As a result, we obtain a lightweight augmentation of the CH data structure that allows for very efficient and visually pleasing rendering of massive road network data.

Most popular speed-up techniques for shortest path queries in road networks are based either on pruned graph search or clever lookup schemes and allow for answering of shortest path distance queries within continent-sized road networks in less than a milli-(search-based) or even microsecond (lookup-based) compared to several seconds of a normal Dijkstra run. While both paradigms previously have been considered mostly separately, we present a framework that unifies these seemingly different views on shortest path computations. Apart from the conceptual novelty, this allows for new and (practically very attractive) space-time tradeoffs for shortest-path computation. To our knowledge we are also the first to report on computational results for the largest connected component of the Open-StreetMap planet road network with more than half a billion nodes.

Hierarchical search such as Contraction Hierarchies is a popular and successful branch of optimization techniques for shortest path computation. Existing hierarchical techniques have one component in common: they add edges to the graph, so called shortcuts. This component usually causes a considerable space overhead but is mandatory in order to preserve correctness. In this work we show a hierarchical method that requires to store only one additional number per node and no shortcuts at all. We prove the correctness of our method and experimentally show that it improves query times by one order of magnitude compared to Dijkstra's bidirectional algorithm.

In a road network with multicriteria edge costs we consider the problem of computing a minimum number of driving preferences such that a given set of paths/trajectories is optimal under at least one of these preferences. While the exact formulation and solution of this problem appears theoretically hard, we show that in practice one can solve the problem exactly even for non-homeopathic instance sizes of several thousand trajectories in a road network of several million nodes. We also present a parameterized guaranteed-polynomial-time scheme with very good practical performance.