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.

Given a set of prioritized balls with fixed centers in ℝd whose radii grow linearly over time, we want to compute the elimination order of these balls assuming that when two balls touch, the one with lower priority is ‘crushed’. A straightforward algorithm has running time O(n2 log n) which we improve to expected O(Δdn(log n + Δd)) where Δ = rmax/rmin is the ratio between largest and smallest radius amongst the balls. For a natural application of this problem, namely drawing labels on the globe, we have Δ = O(1). An efficient implementation based on a spherical Delaunay triangulation allows to compute the elimination order for millions of labels on commodity Desktop hardware. Dealing with rounding error induced robustness issues turned out to be one of the major challenges in the implementation.

We consider the problem of indexing the complete OpenStreetMap planet data set (> 500GB of raw data) to support complex queries involving both text search as well as context-aware spatial relations. This requires (a) formalization of spatial relations like 'north of', 'between', 'near' depending on the context, and (b) the development of suitable data representations to integrate textual and spatial information for efficient query performance.

Each non-zero point in Rd identifies one closest point x on the unit sphere Sd-1. We are interested in computing an ε-approximation y ∈ Qd for x, that is exactly on Sd-1 and has low bit size. We revise lower bounds on rational approximations and provide explicit, spherical instances. We prove that floating-point numbers can only provide trivial solutions to the sphere equation in R2 and R3. Moreover, we show how to construct a rational point with denominators of at most 32(d-1)2/ε2 for any given ε, improving on a previous result. The method further benefits from algorithms for simultaneous Diophantine approximation.