Project B06

Abstract

We present LOOM (Line-Ordering Optimized Maps), a fully automatic generator of geographically accurate transit maps. The input to LOOM is data about the lines of a given transit network, namely for each line, the sequence of stations it serves and the geographical course the vehicles of this line take. We parse this data from GTFS, the prevailing standard for public transit data. LOOM proceeds in three stages: (1) construct a so-called line graph, where edges correspond to segments of the network with the same set of lines following the same course; (2) construct an ILP that yields a line ordering for each edge which minimizes the total number of line crossings and line separations; (3) based on the line graph and the ILP solution, draw the map. As a naive ILP formulation is too demanding, we derive a new custom-tailored formulation which requires significantly fewer constraints. Furthermore, we present engineering techniques which use structural properties of the line graph to further reduce the ILP size. For the subway network of New York, we can reduce the number of constraints from 229,000 in the naive ILP formulation to about 3,700 with our techniques, enabling solution times of less than a second. Since our maps respect the geography of the transit network, they can be used for tiles and overlays in typical map services. Previous research work either did not take the geographical course of the lines into account, or was concerned with schematic maps without optimizing line crossings or line separations.

Abstract

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, and the recent GISCup competition.

Abstract

Current route planning services like Google Maps exhibit a clear-cut separation between the map rendering component and the route planning engine. While both rely on respective road network data, the route planning task is typically performed using state-of-the art data structures for speeding-up shortest/quickest path queries like Hub Labels, Arc Flags, or Transit Nodes, whereas the map rendering task usually involves a rendering framework like Mapnik or Kartograph. In this paper we show how to augment Contraction Hierarchies – another popular data structure for speeding-up shortest path queries – to also cater for the map rendering task. As a result we get a unified data structure (URAN) which lays the algorithmic foundation for novel map rendering and navigation systems. It also allows for customization of the map rendering, e.g. to accommodate different display devices (with varying resolution and hardware capabilities) or routing scenarios. At the heart of our approach lies a generalized graph simplification scheme derived from Contraction Hierarchies with a very lightweight augmentation for extracting (simplified) subgraphs. In a client-server scenario it additionally has the potential to shift the actual route computation to the client side, both relieving the server infrastructure as well as providing some degree of privacy when planning a route.

Abstract

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.

Abstract

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 simple path in G 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 theoretic 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). We also apply our algorithms to other (social, collaboration, web, etc.) networks and can improve in several instances upon previous approaches.

Abstract

Given a set of prioritized disks with fixed centers in R2 whose radii grow linearly over time, we are interested in computing an elimination order of these disks assuming that when two disks touch, the one with lower priority is ‘crushed’. A straightforward algorithm has running time O(n2logn) which we improve to expected O(n(log6n+Δ2log2n+Δ4logn)) where Δ is the ratio between largest and smallest radii amongst the disks. For a very natural application of this problem in the map rendering domain, we have Δ=O(1).