The Pareto sum of two-dimensional point sets P and Q in ℝ² is defined as the skyline of the points in their Minkowski sum. The problem of efficiently computing the Pareto sum arises frequently in bi-criteria optimization algorithms. Prior work establishes that computing the Pareto sum of sets P and Q of size n suffers from conditional lower bounds that rule out strongly subquadratic O(n^{2-ε})-time algorithms, even when the output size is Θ(n). Naturally, we ask: How efficiently can we approximate Pareto sums, both in theory and practice? Can we beat the near-quadratic-time state of the art for exact algorithms? On the theoretical side, we formulate a notion of additively approximate Pareto sets and show that computing an approximate Pareto set is fine-grained equivalent to Bounded Monotone Min-Plus Convolution. Leveraging a remarkable Õ(n^{1.5})-time algorithm for the latter problem (Chi, Duan, Xie, Zhang; STOC '22), we thus obtain a strongly subquadratic (and conditionally optimal) approximation algorithm for computing Pareto sums. On the practical side, we engineer different algorithmic approaches for approximating Pareto sets on realistic instances. Our implementations enable a granular trade-off between approximation quality and running time/output size compared to the state of the art for exact algorithms established in (Funke, Hespe, Sanders, Storandt, Truschel; Algorithmica '25). Perhaps surprisingly, the (theoretical) connection to Bounded Monotone Min-Plus Convolution remains beneficial even for our implementations: in particular, we implement a simplified, yet still subquadratic version of an algorithm due to Chi, Duan, Xie and Zhang, which on some sufficiently large instances outperforms the competing quadratic-time approaches.

Given an input polyline with n vertices, the global polyline simplification problem seeks a simplified polyline with the minimum number of vertices whose distance to the original polyline does not exceed a given bound. For the vertex-restricted variant, where the simplified polyline is required to be a subsequence of the input vertices, an algorithm with a running time of 𝒪(n³) was presented in previous work, using the Fréchet distance as the polyline similarity measure. A closely related variant is the local polyline simplification problem, in which the distance bound is required to hold for every individual shortcut segment replacing a sub-polyline. This condition implies that any locally valid simplification is also globally valid, whereas the converse does not hold. As a consequence, globally optimal simplifications may use substantially fewer vertices than locally optimal ones. Indeed, in previous work, instances were constructed in which the optimal global simplification is smaller by a constant factor. On the algorithmic side, optimal local simplifications can be computed significantly faster, namely in 𝒪(n² log n) under the Fréchet distance, and efficient heuristics are also available. This raises the question of which problem variant is more suitable for practical application. In this paper, we first show that there exist instances for which the optimal solution sizes of global and local polyline simplification differ by a factor in Θ(n), substantially strengthening the previously known constant-factor separation. We then present the first practical implementations of existing algorithms for global polyline simplification and experimentally evaluate their performance. To this end, we introduce several engineering techniques that considerably accelerate these algorithms. Moreover, we develop an implicit Fréchet framework that allows many Fréchet-related problems to be addressed in a weaker computational model. Within this framework, explicit geometric computations can be reduced to simple comparisons, resulting in significantly more robust implementations. Somewhat surprisingly, our experimental results reveal that, despite the large worst-case gap established by our theoretical result, the difference in solution size between optimal global and local simplifications is negligible in practice. Motivated by this observation, we propose a heuristic for global polyline simplification that is guaranteed to produce solutions of size equal to or smaller than the optimal local simplification. On a benchmark consisting of one million polylines, the heuristic yields suboptimal results on only eight while being significantly faster than the optimal algorithms.

Nearest Neighbor Search (NNS) in high-dimensional point sets is an important building block in many application areas, including pattern recognition, machine learning, planning, data mining, and computational geometry. Graph-based approaches that offer approximate NNS (ANNS) are ubiquitously used for these applications, and a variety of suitable graph structures have been proposed for this purpose. However, these approaches do not come with a priori approximation guarantees, often not even in low dimensions. Thus, there may be query points for which the distance to the returned ANN is significantly larger than the distance to the true NN. A common way to assess the quality of graph-based search and to compare different variants is the evaluation of query point samples. However, since the space of potential query points is infinite, it is likely that the samples will give biased results and that critical points will be missed. To systematically evaluate the ANNS quality of a given graph structure, we propose an algorithm that identifies the query point with the worst ratio r between ANN distance and true NN distance. This ratio provides a tight instance-based approximation guarantee. Our algorithm relies on a new geometric data structure called search-path diagram. In our experiments on established base graphs, we demonstrate that sampling based evaluation heavily underestimates r, while our method provides a robust quality assessment.

In this paper, we study the problem of efficiently reporting all intersections between a given set of line segments in the plane and a query circle, focusing on the case where the segments form the edges of a connected geometric graph. While previous data structures for circle-segment intersection queries on general segment sets incur high space or query time costs, we exploit the connectivity of the input to obtain significantly improved performance. In fact, we propose a new circle-segment intersection data structure that can be constructed in 𝒪((n + C) log³ n) time and space on connected graphs with n edges and C edge crossings. It answers intersection queries in 𝒪(k log³ n) time, where k denotes the output size. Our method relies on the construction of efficient circle-graph intersection oracles as well as a novel linear-time algorithm to partition the edges of the graph into balanced, connected components, which might be of independent interest. In a proof-of-concept experimental study on real-world road networks, we show that our novel data structure also performs well in practice. Even on networks with millions of edges, the construction time is within minutes and queries are answered in a few milliseconds.

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.

Abstract In bi-criteria optimization problems, the goal is typically to compute the set of Pareto-optimal solutions. Many algorithms for these types of problems rely on efficient merging or combining of partial solutions and filtering of dominated solutions in the resulting sets. In this article, we consider the task of computing the Pareto sum of two given Pareto sets A, B of size n. The Pareto sum C contains all non-dominated points of the Minkowski sum $$M = \{a+b|a \in A, b\in B\}$$ M = { a + b | a ∈ A , b ∈ B } . Since the Minkowski sum has a size of $$n^2$$ n 2 , but the Pareto sum C can be much smaller, the goal is to compute C without having to compute and store all of M. We present several new algorithms for efficient Pareto sum computation, including an output-sensitive successive algorithm with a running time of $$\mathcal {O}(n \log n + nk)$$ O ( n log n + n k ) and a space consumption of $$\mathcal {O}(n+k)$$ O ( n + k ) for $$k=|C|$$ k = | C | . If the elements of C are streamed, the space consumption reduces to $$\mathcal {O}(n)$$ O ( n ) . For output sizes $$k \ge 2n$$ k ≥ 2 n , we prove a conditional lower bound for Pareto sum computation, which excludes running times in $$\mathcal {O}(n^{2-\delta })$$ O ( n 2 - δ ) for $$\delta > 0$$ δ > 0 unless the (min,+)-convolution hardness conjecture fails. The successive algorithm matches this lower bound for $$k \in \Theta (n)$$ k ∈ Θ ( n ) . However, for $$k \in \Theta (n^2)$$ k ∈ Θ ( n 2 ) , the successive algorithm exhibits a cubic running time. But we also present an algorithm with an output-sensitive space consumption and a running time of $$\mathcal {O}(n^2 \log n)$$ O ( n 2 log n ) , which matches the lower bound up to a logarithmic factor even for large k. Furthermore, we describe suitable engineering techniques to improve the practical running times of our algorithms. Finally, we provide an extensive comparative experimental study on generated and real-world data. As a showcase application, we consider preprocessing-based bi-criteria route planning in road networks. Pareto sum computation is the bottleneck task in the preprocessing phase and in the query phase. We show that using our algorithms with an output-sensitive space consumption allows to tackle larger instances and reduces the preprocessing and query time compared to algorithms that fully store M.

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.

Given a directed graph G(V, A), the DIRECTED FEEDBACK VERTEX SET (DFVS) problem asks for the smallest sized subset of V whose removal makes G acyclic. The problem is NP-complete and efficient constant-factor approximation algorithms are ruled out under UGC. Attempting to get an exact DFVS in practice usually involves the application of reduction rules that decrease the instance size without compromising the optimal solution. If the reduced graph gets sufficiently small, the respective instance can then be solved to optimality e.g. by a branching algorithm. However, one might need to resort to heuristics in the end in case the reduced instance is still huge. In this paper, we propose novel reduction rules for DFVS with a special focus on lossy rules. Here, the idea is that an optimal solution on the reduced graph combined with the information gained in the reduction process provides an α-approximation for the original instance. We present several rules that ensure small α, and discuss how to combine and engineer them. We also propose a taxonomy to study general types of lossy rules. In an extensive experimental analysis, we evaluate the impact of exact and lossy rules on the running time, the size of the reduced instance, and the solution quality. It turns out that the lossy rules are indeed very effective and that it is often possible to solve instances by using reduction rules only.

Abstract Euler diagrams are a popular technique to visualize set‐typed data. However, creating diagrams using simple shapes remains a challenging problem for many complex, real‐life datasets. To solve this, we propose RectEuler: a flexible, fully‐automatic method using rectangles to create Euler‐like diagrams. We use an efficient mixed‐integer optimization scheme to place set labels and element representatives (e.g., text or images) in conjunction with rectangles describing the sets. By defining appropriate constraints, we adhere to well‐formedness properties and aesthetic considerations. If a dataset cannot be created within a reasonable time or at all, we iteratively split the diagram into multiple components until a drawable solution is found. Redundant encoding of the set membership using dots and set lines improves the readability of the diagram. Our web tool lets users see how the layout changes throughout the optimization process and provides interactive explanations. For evaluation, we perform quantitative and qualitative analysis across different datasets and compare our method to state‐of‐the‐art Euler diagram generation methods.

In this paper, we consider the problem of gradual road network simplification, where given an embedded road network the goal is to compute a fine-grained succession of simplifications with decreasing level-of-detail. This allows to render the network on any desired zoom level or with a user-defined number of segments. Previous work has established that this can be achieved based on a Contraction Hierarchies (CH) data structure. CH was originally developed as a graph preprocessing method to speed up shortest path planning in road networks. However, since it is inherently based on a graph simplification mechanism, it can also serve as a basis for rendering. But the existing method exhibits several shortcomings, for example, topological inconsistencies arise on many simplification levels and the preservation of the shape of routes and the overall network for coarser graph representations is insufficient. This severely impairs the navigability of the map. We significantly improve upon the existing method by modifying the CH construction process as well as the rendering algorithm.

Measuring the similarity of spatio-temporal trajectories in a sensible fashion is an important building block for applications such as trajectory clustering or movement pattern analysis. However, typically employed similarity measures only take the spatial components of the trajectory into account, or are complicated combinations of different measures. In this paper we introduce the so called Generalized Fréchet distance, which extends the well-known Fréchet distance. For two polygonal curves of length n and m in d-dimensional space, the Generalized Fréchet distance enables an individual weighting of each dimension on the similarity value by using a convex function. This allows to integrate arbitrary data dimensions as e.g. temporal information in an elegant, flexible and application-aware manner. We study the Generalized Fréchet Distance for both the discrete and the continuous version of the problem, prove useful properties, and present efficient algorithms to compute the decision and optimization problem. In particular, we prove that for d ∈ O(1) the asymptotic running times of the optimization problem for the continuous version are O(nm log(nm)) under realistic assumptions, and O(nm) for the discrete version for arbitrary weight functions. Therefore the theoretical running times match those of the classical Fréchet distance. In our experimental evaluation, we demonstrate the usefulness of the Generalized Fréchet distance and study the practical behaviour of our algorithms. On sets of real-world trajectories, we confirm that the weighting of the spatial and temporal dimensions heavily impacts the relative similarity, and hence the ability to tailor the measure to the application is a useful tool.

We instrument Group Diagrams (GDs) to reduce clutter in sets of eye-tracking scanpaths. Group Diagrams consist of trajectory subsets that cover, or represent, the whole set of trajectories with respect to some distance measure and an adjustable distance threshold. The original GDs allow for an application of various distance measures. We implement the GD framework and evaluate it on scanpaths that were collected by a former user study on public transit maps. We find that the Fréchet distance is the most appropriate measure to get meaningful results, yet it is flexible enough to cover outliers. We discuss several implementation-specific challenges and improve the scalability of the algorithm.

We present a holistic approach for pedestrian routing that allows computing shortest paths that may have indoor and outdoor sections. Such routes arise, for example, when the destination is not just an address but a specific store in a large mall, or when one needs to get to a certain track at a large train station. Currently, map services as Google Maps or OSRM do not offer such functionality. We identify and overcome three main challenges for answering such complex route planning queries: (i) Pedestrian routing requires fine-grained data, as the location of stairs and elevators, building dventrances, building footprints, and elevation/level information. A single missing staircase can change the length of the computed path severely. (ii) Indoor routing has to be integrated carefully into classical path planning to allow the computation of sensible routes that may enter and exit buildings. (iii) Given the large amount of data to be considered in a query, acceleration techniques need to be applied in order to achieve interactive query times. Retrieving barrier-free routes for wheelchairs is also our important use case.

A k nearest neighbors (kNN) query finds k closest points-of-interest (POIs) from an agent's location. In this paper, we study a natural extension of the kNN query for multiple agents, namely, the Aggregate k Nearest Neighbors (AkNN) query. An AkNN query retrieves k POIs with the smallest aggregate distances where the aggregate distance of a POI is obtained by aggregating its distances from the multiple agents (e.g., sum of its distances from each agent). We propose a novel data structure COLT (Compacted Object-Landmark Tree) which enables efficient hierarchical graph traversal and utilize it to efficiently answer AkNN queries. Our experiments on real-world and synthetic data sets show that our techniques outperform existing approaches by more than an order of magnitude in almost all settings.

We present new generic methods to efficiently draw schematized metro maps for a wide variety of layouts, including octilinear, hexalinear, and orthoradial maps. The maps are drawn by mapping the input graph to a suitable grid graph. Previous work was restricted to regular octilinear grids. In this work, we investigate a variety of grids, including triangular grids and orthoradial grids. In particular, we also construct sparse grids where the local node density adapts to the input graph (e.g. octilinear Hanan grids, which we introduce in this work). For octilinear maps, this reduces the grid size by a factor of up to 5 compared to previous work, while still achieving close-to-optimal layouts. For many maps, this reduction also leads to up to 5 times faster solution times of the underlying optimization problem. We evaluate our approach on five maps. All octilinear maps can be computed in under 0.5 seconds, all hexalinear and orthoradial maps can be computed in under 2.5 seconds.

We present a pipeline that, given a weighted graph as an input, produces a planar grid embedding where all edges are represented as axis-aligned straight lines with their Euclidean length matching their edge weight (if such an embedding exists). Being able to compute such embeddings is important for visualization purposes but is additionally helpful to solve certain optimization problems faster, as e.g. the Steiner tree problem. Our embedding pipeline consists of three main steps: In the first step, we identify rigid substructures which we call puzzle pieces. In the second step, we merge puzzle pieces if possible. In the third and last step, we compute the final embedding (or decide that such an embedding does not exist) via backtracking. We describe suitable data structures and engineering techniques for accelerating all steps of the pipeline along the way. Experiments on a large variety of input graphs demonstrate the applicability and scalability of our approach.

The BahnCard problem is an important problem in the realm of online decision making. In its original form, there is one kind of BahnCard associated with a certain price, which upon purchase reduces the ticket price of train journeys for a certain factor over a certain period of time. The problem consists of deciding on which dates BahnCards should be purchased such that the overall cost, that is, BahnCard prices plus (reduced) ticket prices, is minimized without having knowledge about the number and prices of future journeys. In this paper, we extend the problem such that multiple kinds of BahnCards are available for purchase. We provide an optimal offline algorithm, as well as online strategies with provable competitiveness factors. Furthermore, we describe and implement several heuristic online strategies and compare their competitiveness in realistic scenarios.

Contraction hierarchies (CH) is a prominent preprocessing-based technique that accelerates the computation of shortest paths in road networks by reducing the search space size of a bidirectional Dijkstra run. To explain the practical success of CH, several theoretical upper bounds for the maximum search space size were derived in previous work. For example, it was shown that in minor-closed graph families search space sizes in 𝒪(√n) can be achieved (with n denoting the number of nodes in the graph), and search space sizes in 𝒪(h log D) in graphs of highway dimension h and diameter D. In this paper, we primarily focus on lower bounds. We prove that the average search space size in a so called weak CH is in Ω(b_α) for α ≥ 2/3 where b_α is the size of a smallest α-balanced node separator. This discovery allows us to describe the first approximation algorithm for the average search space size. Our new lower bound also shows that the 𝒪(√n) bound for minor-closed graph families is tight. Furthermore, we deeper investigate the relationship of CH and the highway dimension and skeleton dimension of the graph, and prove new lower bound and incomparability results. Finally, we discuss how lower bounds for strong CH can be obtained from solving a HittingSet problem defined on a set of carefully chosen subgraphs of the input network.

Abstract Schematic transit maps (often called “metro maps” in the literature) are important to produce comprehensible visualizations of complex public transit networks. In this work, we investigate the problem of automatically drawing such maps on an octilinear grid with an arbitrary (but optimal) number of edge bends. Our approach can naturally deal with obstacles that should be respected in the final drawing (points of interest, rivers, coastlines) and can prefer grid edges near the real‐world course of a line. This allows our drawings to be combined with existing maps, for example as overlays in map services. We formulate an integer linear program which can be used to solve the problem exactly. We also provide a fast approximation algorithm which greedily calculates shortest paths between node candidates on the underlying octilinear grid graph. Previous work used local search techniques to update node positions until a local optimum was found, but without guaranteeing octilinearity. We can thus calculate nearly optimal metro maps in a fraction of a second even for complex networks, enabling the interactive use of our method in map editors.

In this paper, we study a problem from the realm of multicriteria decision making in which the goal is to select from a given set S of d-dimensional objects a minimum sized subset S0 with bounded regret. Thereby, regret measures the unhappiness of users which would like to select their favorite object from set S but now can only select their favorite object from the subset S0. Previous work focused on bounding the maximum regret which is determined by the most unhappy user. We propose to consider the average regret instead which is determined by the sum of (un)happiness of all possible users. We show that this regret measure comes with desirable properties as supermodularity which allows to construct approximation algorithms. Furthermore, we introduce the regret minimizing permutation problem and discuss extensions of our algorithms to the recently proposed k-regret measure. Our theoretical results are accompanied with experiments on a variety of inputs with d up to 7.

We consider the problem of computing a set of alternative routes in a multicriteria setting where several network metrics are available. Previous approaches for alternative route computation were based on relaxing a single metric to obtain alternative routes whereas our approach for the multicriteria setting produces routes that are always optimal for a convex combination of the metrics. For the concrete example of route planning for bicycles with three natural metrics (distance, positive height difference, unsuitability for cycling) we show. how to efficiently generate very natural alternative bicycle routes.

Given a directed graph G(V,E), a k-(Shortest) Path Cover is a subset C of the nodes V such that every simple (or shortest) path in G consisting of k nodes contains at least one node from C. In this paper, we extend the notion of k-Path Covers such that the objects to be covered don't have to be single paths but can be concatenations of up to p simple (or shortest) paths. For the generalized problem of computing concatenated k-(Shortest) Path Covers, we present theoretical results regarding the VC-dimension of the concatenated path set in dependency of p as well as (approximation) algorithms. Subsequently, we study interesting special cases of concatenated k-Path Covers, in particular, covers for piecewise shortest paths, round tours and trees. For those, we show how the pruning algorithm for k-Path Cover computation can be abstracted and modified in order to also solve concatenated k-Path Cover problems. An extensive experimental study on different graph types proves the applicability and efficiency of our approaches.

Graph sparsification has been used to improve the computational cost of learning over graphs, e.g., Laplacian-regularized estimation and graph semi-supervised learning (SSL). However, when graphs vary over time, repeated sparsification requires polynomial order computational cost per update. We propose a new type of graph sparsification namely fault-tolerant (FT) sparsification to significantly reduce the cost to only a constant. Then the computational cost of subsequent graph learning tasks can be significantly improved with limited loss in their accuracy. In particular, we give theoretical analyze to upper bound the loss in the accuracy of the subsequent Laplacian-regularized estimation and graph SSL, due to the FT sparsification. In addition, FT spectral sparsification can be generalized to FT cut sparsification, for cut-based graph learning. Extensive experiments have confirmed the computational efficiencies and accuracies of the proposed methods for learning on dynamic graphs.

In this paper, we study a problem from the realm of multi-criteria decision making in which the goal is to select from a given set S of d-dimensional objects a minimum sized subset S' with bounded regret. Thereby, regret measures the unhappiness of users which would like to select their favorite object from set S but now can only select their favorite object from the subset S'. Previous work focused on bounding the maximum regret which is determined by the most unhappy user. We propose to consider the average regret instead which is determined by the sum of (un)happiness of all possible users. We show that this regret measure comes with desirable properties as supermodularity which allows to construct approximation algorithms. Furthermore, we introduce the regret minimizing permutation problem and discuss extensions of our algorithms to the recently proposed k-regret measure. Our theoretical results are accompanied with experiments on a variety of inputs with d up to 7.

We consider the problem of indexing massive trajectory data in an underlying road network. Our Pathfinder index structure is based on a state-of-the-art speed-up technique for shortest path planning and allows to both compress and access huge amounts of trajectory data. In a continent-sized network with more than 400 million nodes and almost a billion edges, Pathfinder allows to retrieve all trajectories within a given space-time cube in a few microseconds per reported trajectory. The applicability of Pathfinder is shown using both synthetic and real-world trajectory sets.

Shortest path planning is a fundamental building block in many applications. Hence developing efficient methods for computing shortest paths in e.g. road or grid networks is an important challenge. The most successful techniques for fast query answering rely on preprocessing. But for many of these techniques it is not fully understood why they perform so remarkably well and theoretical justification for the empirical results is missing. An attempt to explain the excellent practical performance of preprocessing based techniques on road networks (as transit nodes, hub labels, or contraction hierarchies) in a sound theoretical way are parametrized analyses, e.g., considering the highway dimension or skeleton dimension of a graph. But these parameters tend to be large (order of Θ(√n)) when the network contains grid-like substructures — which inarguably is the case for real-world road networks around the globe. In this paper, we use the very intuitive notion of bounded growth graphs to describe road networks and also grid graphs. We show that this model suffices to prove sublinear search spaces for the three above mentioned state-of-the-art shortest path planning techniques. For graphs with a large highway or skeleton dimension, our results turn out to be superior. Furthermore, our preprocessing methods are close to the ones used in practice and only require randomized polynomial time.

We present CYCLOPS, a route planning system for cyclists that allows for intuitive specification of preferences for a route query, and also suggests several alternative route options. It combines three metrics of the underlying road network relevant to cyclists (distance, positive height gain, unsuitability for cycling), to cater for different cycling habits. The CYCLOPS back end is based on state-of-the-art multi-criteria route planning techniques, the front end is realized using the HTML5 Canvas API to provide an intuitive interface for combining metrics in personalized route planning queries and a visualization of the routes found.

We present LOOM (Line-Ordering Optimized Maps), an automatic generator of geographically accurate transit maps. The input to LOOM is data about the lines of a transit network: for each line, its station sequence and geographical course. LOOM proceeds in three stages: (1) construct a line graph, where edges correspond to network segments with the same set of lines following the same course; (2) apply a set of local transformation rules that compute an optimal partial ordering of the lines and speed up the next stage; (3) construct an Integer Linear Program (ILP) that yields a line ordering for each edge and minimizes the total number of line crossings and line separations; and (4) based on the line graph and the computed line ordering, draw the map. As our maps respect the geography of the transit network, they can be used as overlays in typical map services. Previous research either did not take the network geography into account or was only concerned with schematic metro map layouting. We evaluate LOOM on six real-world transit networks, with line-ordering search-space sizes up to 2 × 10 267 . Using our transformation rules and an improved ILP formulation, we compute optimal line orderings in a fraction of a second for all networks. This enables interactive use of our method in map editors.

Real-world route planning problems are conventionally modeled as weighted graphs - either as grid graphs for open spaces or as path/road networks. The edge weights (e.g. Euclidean distances, travel times or energy consumption) are then derived from measurements or estimations. But the resulting weights are often overly precise and demand a lot of space to be stored. In addition, operations on these weights are computationally expensive. The common approach to avoid those problems is to round edge weights to reasonable precisions (e.g. whole meters, seconds or watt). Unfortunately, naive rounding schemes can easily distort the structure of optimal paths in the graph. In this paper, we present a novel rounding framework based on the construction of an overlay graph. We show that a carefully designed overlay graph based on so called contraction hierarchies can accelerate shortest path computations and minimize rounding errors at the same time, while demanding little space on its own.

A grid maze is a binary matrix where fields containing a 0 are accessible while fields containing a 1 are blocked. A movement sequence consists of relative movements up, down, left, right – moving to a blocked field results in non-movement. The simultaneous maze solving problem asks for the shortest movement sequence starting in the upper left corner and visiting the lower right corner for all mazes of size n × m (for which a path from the upper left to the lower right corner exists at all). We present a theoretical problem analysis, including hardness results and a cubic upper bound on the sequence length. In addition, we describe several approaches to practically compute solving sequences and lower bounds despite the high combinatorial complexity of the problem.

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 classical line simplification problem subject to a given error bound ∊ but with additional topology constraints as they arise for example in the map rendering domain. While theoretically inapproximability has been proven for these problem variants, we show that in practice one can solve medium sized instances optimally using an integer linear programming approach and larger instances using an heuristic approach which for medium-sized real-world instances yields close-to-optimal results. Our approaches are evaluated on data sets which are synthetically generated, stem from the OpenStreetMap project[1], and the recent GISCup competition [3].

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.

We consider the problem of generating concise and robust driving directions that avoid overly detailed turn-by-turn instructions as long as one is not too close to the final destination. Our approach is based on a deliberate selection of cities as landmarks that are likely to appear on road signs along the route. For a route from Stuttgart to Flensburg, the route description could read "Go towards Frankfurt, then Kassel, then Hanover, then Hamburg". Apart from being more compact, such driving directions are also more robust against wrong turns taken. While an implementation based on Dijkstra's algorithm takes on the order of several seconds to generate such driving directions, a careful instrumentation of speed-up techniques reduces this to fractions of a second required, e.g., for a web service.

In a personalized route planning query, a user can specify how relevant different criteria as travel time, gas consumption, scenicness, etc. are for his individual definition of an optimal route. Recently developed acceleration schemes for personalized route planning, which rely on preprocessing, achieve a significant speed-up over the Dijkstra baseline for a small number of criteria. But for more than five criteria, either the preprocessing becomes too complicated or the query answering is slow. In this paper, we first present a new LP-based preprocessing technique which allows to deal with many criteria efficiently. In addition, we show how to further reduce query times for all known personalized route planning acceleration schemes by considering approximate queries. We design a data structure which allows not only to have personalized costs but also individual approximation guarantees per query, allowing to trade solution quality against query time at the user's discretion. This data structure is the first to enable a speed-up of more than 100 for ten criteria while accepting only 0.01% increased costs.

We consider the problem of Pareto-optimal route planning in public-transit networks of a whole country, a whole continent, or even the whole world. On such large networks, existing approaches suffer from either a very large space consumption, a very long preprocessing time or slow query processing. Transfer Patterns, a state-of-the-art technique for route planning in transit networks, achieves excellent query times, but the space consumption is large and the preprocessing time is huge. In this paper, we introduce a new scheme for the Transfer Pattern precomputation and query graph construction that reduces both the necessary preprocessing time and space consumption by an order of magnitude and more. Average query times are below 1 ms for local queries, independent of the size of the network, around 30 ms for non-local queries on the complete transit network of Germany, and an estimated 200 ms for a fictitious transit network covering the currently available data of the whole world.

We study the problem of learning individual route preferences of drivers. Most current route planning services only compute shortest or quickest paths. But many other criteria might play a role for a user to prefer a certain route, as, e.g., fuel consumption, jam likeliness, road conditions, scenicness of the route, turns, allowed maximum speeds, toll costs and many more. Specifying the importance of each criterion manually is a non-trivial, unintuitive and time consuming undertaking for a user. Therefore, we develop approaches that deduce such preferences automatically based on paths previously driven by the user. We present an LP-formulation of the problem making use of a Dijkstra-based separation oracle. The resulting algorithm runs in polynomial time and allows for the user preference computation in few seconds even if several hundred routes are taken into account. Our experiments show that new route suggestions based on these learned preferences reflect the users definition of an optimal route very well.

Often, the edge weights of graphs are given in implicitly infinite or overly high precision (think of Euclidean lengths) which leads to both theoretical as well as practical challenges. In this paper we investigate how to round edge weights of a given graph G(V,E,w) such that the rounded weights of paths satisfy certain consistency criteria. Natural consistency criteria are, for example, preserving optimality of paths, and bounding relative change in weight after the rounding procedure. Low precision edge weights allow for more space efficient implementations, faster arithmetic operations, and in general more stable and efficient algorithms. We present an ILP based rounding approach as well as a greedy rounding heuristic. We show experimentally for large road networks and grid graphs that our new rounding approaches are significantly better than common deterministic or randomized rounding schemes.

We show how to estimate population numbers for arbitrary user-defined regions, down to the level of individual buildings. This is important for various applications like evacuation planning, facility placement, or traffic estimation. However, census data with precise population numbers is typically only available at the level of cities, villages, or districts, if at all.

Computing shortest paths in road networks with millions of nodes and edges is challenging on its own. In the last few years, several preprocessing-based acceleration techniques have been developed to enable query answering orders of magnitudes faster than a plain Dijkstra computation. But most of these techniques work only if the metric which determines the optimal path is static or rarely changes. In contrast to that, we aim at answering personalized route planning queries. Here, every single query comes with a specification of its very own metric. This increases the combinatorial complexity of the problem significantly. We develop new preprocessing schemes that allow for real-time personalized route planning in huge road networks while keeping the memory footprint of the preprocessed data and subsequent queries small.

Compared to conventional cars, electric vehicles (EVs) still suffer from considerably shorter cruising ranges. Combined with the sparsity of battery loading stations, the complete transition to E-mobility still seems a long way to go. In this paper, we consider the problem of placing as few loading stations as possible so that on any shortest path there are sufficiently many not to run out of energy. We show how to model this problem and introduce heuristics which provide close-to-optimal solutions even in large road networks.

Compared to conventional cars, electric vehicles still suffer from a considerably shorter cruising range. Combined with the sparsity of battery loading stations, the complete transition to E-mobility still seems a long way to go. In this paper, we consider the problem of placing as few loading stations as possible such that on any shortest path there are enough to guarantee sufficient energy supply. This means, that EV owners no longer have to plan their trips ahead incorporating loading station locations, and are no longer forced to accept long detours to reach their destinations. We show how to model this problem and introduce heuristics which provide close-to-optimal solutions even in large road networks.

Public-transportation route-planning systems typically work as follows. The user specifies a source and a target location, as well as a departure time. The system then returns one or more optimal trips at or after that departure time. In this paper, we consider guidebook routing, where the goal is to provide time-independent answers that are valid over long periods of time. An example answer could be: Take Bus 10 to the main station, from there take Tram 11 or 13 (whichever comes next) to your target station. Trip duration: 30 minutes. Frequency: every 20 minutes. Valid: weekdays from 6am – 8pm. We show how to compute such guidebook routes efficiently and with provably good quality. An evaluation on real-world data shows that few guidebook routes usually suffice for good coverage. We also show how guidebook routing can be used to speed up transfer patterns, a state-of-the-art method for public transportation routing.

We introduce a framework to create a world-wide live map of public transit, i.e. the real-time movement of all buses, subways, trains and ferries. Our system is based on freely available General Transit Feed Specification (GTFS) timetable data and also features real-time delay information (where available). The main problem of such a live tracker is the enormous amount of data that has to be handled (millions of vehicle movements). We present a highly efficient back-end that accepts temporal and spatial boundaries and returns all relevant trajectories and vehicles in a format that allows for easy rendering by the client. The real-time movement visualization of complete transit networks allows to observe the current state of the system, to estimate the transit coverage of certain areas, to display delays in a neat manner, and to inform a mobile user about near-by vehicles. Our system can be accessed via http://tracker.geops.ch/. The current implementation features over 80 transit networks, including the complete Netherlands (with real-time delay data), and various metropolitan areas in the US, Europe, Australia and New Zealand. We continuously integrate new data. Especially for Europe and North America we expect to achieve almost full coverage soon.

We present TRAVIC, a thin browser-based client that is able to display smooth vehicle movements on a map. The focus is on visualizing world-wide public transit vehicle movements in an interactive way. But we also investigate other use cases, for example, traffic simulation. We describe in detail which server requests are fired and how the received data is handled. We also provide a performance evaluation conducted on several browsers. We show that, in combination with an efficient back-end, TRAVIC is able to display many thousands of vehicle movements in real-time. Our prototype implementation can be accessed under http://tracker.geops.ch.

We consider the application of route planning in large public-transportation networks (buses, trains, subways, etc). Many connections in such networks are operated at periodic time intervals. When a set of connections has sufficient periodicity, it becomes more efficient to store the time range and frequency (e.g., every 15 minutes from 8:00am-6:00pm) instead of storing each of the time events separately. Identifying an optimal frequency-compression is NP-hard, so we present a time- and space-efficient heuristic.

For a directed graph G with vertex set V we call a subset C ⊆ V a k-(All-)Path Cover if C contains a node from any path consisting of k nodes. This paper considers the problem of constructing small k -Path Covers in the context of road networks with millions of nodes and edges. In many application scenarios the set C and its induced overlay graph constitute a very compact synopsis of G which is the basis for the currently fastest data structure for personalized shortest path queries, visually pleasing overlays of subsampled paths, and efficient reporting, retrieval and aggregation of associated data in spatial network databases. Apart from a theoretical investigation of the problem, we provide efficient algorithms that produce very small k -Path Covers for large real-world road networks (with a posteriori guarantees via instance-based lower bounds).

The short cruising range due to the limited battery supply of current Electric Vehicles (EVs) is one of the main obstacles for a complete transition to E-mobility. Until batteries ofhigher energy storage density have been developed, it is of utmost importance to deliberately plan the locations of new loading stations for best possible coverage. Ideally the network of loading stations should allow driving from anywhere to anywhere (and back) without running out of energy. We show that minimizing the number of necessary loading stations to achieve this goal is NP-hard and even worse, we can rule out polynomial-time constant approximation algorithms. Hence algorithms with better approximation guarantees have to make use of the special structure of road networks (which is not obvious how to do it). On the positive side, we show with instance based lower bounds that our heuris-tic algorithms achieve provably good solutions on real-world problem instances.

We consider multicriteria shortest path problems and show that contraction hierarchies — a very powerful speed-up technique originally developed for standard shortest path queries in [7] — can be constructed efficiently for the case of arbitrary conic combinations of the edge costs. This extends previous results in [5] which considered only the bicriteria case and discrete weights for the objective functions. On the theory side we prove a polynomial time bound for determining whether a path π is part of the lower envelope of all pareto-optimal paths via some polyhedral arguments. Experiments complement these results by showing the practicability of our approach.

We study multi-modal route planning allowing arbitrary (meaningful) combinations of public transportation, walking, and taking a car / taxi. In the straightforward model, the number of Pareto-optimal solutions explodes. It turns out that many of them are similar to each other or unreasonable. We introduce a new filtering procedure, Types aNd Thresholds (TNT), which leads to a small yet representative subset of the reasonable paths. We consider metropolitan areas like New York, where a fast computation of the paths is difficult. To reduce the high computation times, optimality-preserving and heuristic approaches are introduced. We experimentally evaluate our approach with respect to result quality and query time. The experiments confirm that our result sets are indeed small (around 5 results per query) and representative (among the reasonable Pareto-optimal paths), and with average query times of about one second or less.

Transfer pattern routing is a state-of-the-art speed-up technique for finding optimal paths which minimize multiple cost criteria in public transportation networks. It precomputes sequences of transfer stations along optimal paths. At query time, the optimal paths are searched among the stored transfer patterns, which allows for very fast response times even on very large networks. On the other hand, even a minor change to the timetables may affect many optimal paths, so that, in principle, a new computation of all optimal transfer patterns becomes necessary. In this paper, we examine the robustness of transfer pattern routing towards delay, which is the most common source of such updates. The intuition is that the deviating paths caused by typical updates are already covered by original transfer patterns. We perform experiments which show that the transfer patterns are remarkably robust even to large and many delays, which underlines the applicability and reliability of transfer pattern routing in realistic routing applications.

Timetable information in public transportation networks exhibit a large degree of redundancy; e.g. consider a bus going from station A to station B at 6:00, 6:15, 6:30, 6:45, 7:00, 7:15, 7:30, . . . , 20:00, the very same data can be provided by a frequency-based representation as ’6:00-20:00, every 15 minutes’ in considerably less space. Nevertheless a common graph model for routing in public transportation networks is the time-expanded representation where for each arrival/departure event a single node is created. We will introduce a frequency-based graph model which allows for a significantly more compact representation of the network, resulting also in a speed-up for station-to-station queries. Moreover we will describe a new variant of Dijkstra’s algorithm, where also the labels are frequency-based. This approach allows for accelerating profile queries in public transportation networks.

In this paper we consider a variant of the multi-criteria shortest path problem where the different criteria are combined in an arbitrary conic combination at query time. We show that contraction hierarchies (CH) — a very powerful speed-up technique originally developed for standard shortest path queries (Geisberger et al. 2008) — can be adapted to this scenario and lead - after moderate preprocessing effort - to query times that are orders of magnitudes faster than standard shortest path approaches. On the theory side we prove via some polyhedral considerations that the crucial node contraction operation during the CH construction can be performed in polynomial-time, while on the more practical side we complement our theoretical results with experiments on real-world data. Our approach extends previous results (Geisberger, Kobitzsch, and Sanders 2010) which only considered the bicriteria case. This is an extended abstract of the full paper published in (Funke and Storandt 2013).

Many speed-up techniques developed for accelerating the computation of shortest paths in road networks, like reach or contraction hierarchies, are based on the property that some streets are ’more important’ than others, e.g. on long routes the usage of an interstate is almost inevitable. In grids there is no obvious hierarchy among the edges, especially if the costs are uniform. Nevertheless we will show that contraction hierarchies can be applied to grid graphs as well. We will point out interesting connections to speed-up techniques shaped for routing on grids, like swamp hierarchies and jump points, and provide experimental results for game maps, mazes, random grids and rooms.

The main hindrance to a widespread market penetration of battery-powered electric vehicles (BEVs) has been their limited energy reservoir resulting in cruising ranges of few hundred kilometers unless one allows for recharging or switching of depleted batteries during a trip. Unfortunately, recharging typically takes several hours and battery switch stations providing fully recharged batteries are still quite rare – certainly not as widespread as ordinary gas stations. For not getting stranded with an empty battery, going on a BEV trip requires some planning ahead taking into account energy characteristics of the BEV as well as available battery switch stations. In this paper we consider very basic, yet fundamental problems for E-Mobility: Can I get from A to B and back with my BEV without recharging in between? Can I get from A to B when allowed to recharge? How can I minimize the number of battery switches when going from A to B? We provide efficient and mathematically sound algorithms for these problems that allow for the energy-aware planning of trips.

In this paper we consider two challenging problems that arise in the context of computing a consensus of a collection of multilabeled trees, namely (1) selecting a compatible collection of clusters on a multiset from an ordered list of such clusters and (2) optimally refining high degree vertices in a multilabeled tree. Forming such a consensus is part of an approach to reconstruct the evolutionary history of a set of species for which events such as genome duplication and hybridization have occurred in the past. We present exact algorithms for solving (1) and (2) that have an exponential runtime in the worst case. To give some impression of their performance in practice, we apply them to simulated input and to a real biological data set highlighting the impact of several structural properties of the input on the performance.

We consider the problem of routing electric vehicles (EV) in the most energy-efficient way within a road network taking into account both their limited energy supply as well as their ability to recuperate energy. Employing a classical result by Johnson and an observation about Dijkstra under non-constant edge costs we obtain O(n log n +m) query time after a O(nm) preprocessing phase for any road network graph whose edge costs represent energy consumption or recuperation.If the energy recuperation is height induced in a very natural way,the preprocessing phase can even be omitted. We then adapt a technique for speeding-up (unconstrained) shortest path queries to our scenario to achieve a speed-up of another factor of around 20. Our results drastically improve upon the recent results in (Artmeier et al. 2010) and allow for route planning of EVs in an instant even on large networks.

We consider the following two problems: Map Matching: Given a sequence of (imprecise) location measurements from a mobile user moving on a road network, determine the most likely path in the network this user has travelled along. Prediction of Trajectories: Given the path of where a mobile user has moved along in a road network up to now, predict where he will travel along in the near future. Our map matching algorithm is simple and efficient even in case of very imprecise measurements like GSM-localizations and allows for the real-time tracking of a large number of mobile users on modest hardware. Our proposed path prediction algorithm is equally simple but yields extremely accurate predictions at a very low computational cost.

We propose a novel scheme for map matching and fully autonomous self-localization. Our scheme is based on the unique characteristics of the shape of paths in a road network. As uniqueness of path shapes comes as no surprise in a world of infinite precision, we develop robust means of comparing shapes of paths under imprecisions. Even under this fuzzy comparison model, path shapes turn out to be sufficiently characteristic to allow for map matching or fully autonomous self-localization. We design an efficient data structure which allows for very fast path shape queries.