Research on map generalization has led to many algorithms for multiple elementary processes, such as object selection, aggregation, simplification, and displacement. Algorithms for different processes are usually combined to workflows or orchestrated using multi-agent systems. Here, we present a novel approach integrating object selection and displacement at an algorithmic level. We model both processes together as an optimization problem in the form of a mixed-integer quadratic program and demonstrate that it can be optimally solved using a mathematical problem solver. Moreover, we present an efficient heuristic. In experiments with roads and buildings from OpenStreetMap, our methods showed a good capability to unselect a small set of buildings whose inclusion in the output map would have caused large displacements or proximity conflicts. For a quantitative evaluation, we solved a benchmark instance once with our new model integrating selection and displacement and once with a variant of our model where the selection of objects was prescribed based on a solution found with an existing approach via simulated annealing. Comparing the two models, our integrated model yielded a solution of 33% less total cost. We conclude the article with a discussion of possible follow-up work.

Attractive cycling routes can effectively promote active mobility, thus reducing the twin pressures of the population boom and the greenhouse effect. However, the existing approaches for cycling route recommendation primarily concentrate on identifying the most efficient routes while ignoring the urban spatial context, which is essential to meet the user’s particular preferences. This article proposes a novel method for informed sampling and recommending cycling routes leveraging crowd-sourced trajectories with weighted-latent Dirichlet allocation (WLDA). Precisely, spatial context mapping, incorporating a weighting mechanism into LDA, latent topics mining, and cycling route recommendation based on informed sampling are introduced. We collected 1,016 cycling trajectories around Cologne, Germany, for experimental analysis. The experimental results show that the three latent topics within the trajectories, leisure, city, and green tours, are clearly presented in the line density analysis. The insightful recommendation for unfamiliar cyclists could also be actively sampled upon the WLDA model. These findings suggest that our approach could shift the route recommendation paradigm from GIS analysis to a semantic mining perspective, yielding highly interpretable results and offering novel research avenues for applying machine learning in route planning.

Integrating landmarks into the communication of wayfinding services is an established strategy that enhances wayfinding efficiency and user confidence. In this context, we present a strategy for selecting landmarks for route descriptions that keeps the number of selected landmarks small. We argue that limiting the number of landmarks to be referred to in a route description can help to reduce the length and complexity of the description. Instead of selecting a different landmark located at each decision point, we reduce the selection to landmarks that can be seen from multiple decision points. We preferably choose those landmarks that are already clearly visible when approaching a decision point, thus optimizing advance visibility. We formalize an optimization problem that requires that at least one selected landmark is visible from each decision point. While minimizing the number of selected landmarks, we aim to maximize their advance visibility along the route. We show that our problem is NP-hard and present both an exact approach that uses integer linear programming and a greedy heuristic. In our experiments, we demonstrate that our approach can substantially reduce the number of selected landmarks compared to a baseline strategy. We determine a compromise between the optimization criteria and show that the heuristic generates high-quality solutions within a short running time.

Ever since location-based services and mobile applications collecting data gathered through Global Navigation Satellite System (GNSS) positioning have become popular, concerns about location privacy have been expressed. Research has shown that human trajectory repositories containing sequences of observed locations ordered in time constitute a rich source for analyzing movement patterns, but they can also reveal sensitive personal information, such as a person’s home address. In this paper, we present a mechanism that protects visits to sensitive locations by suppressing revealing parts of trajectories. Our attack model acknowledges that the course of a trajectory, combined with spatial context information, can facilitate privacy breaches even if sensitive locations have been concealed. Thus, we introduce the concept of k-site-unidentifiability, a specialization of k-anonymity, under which a sensitive location cannot be singled out from a group of at least k sites that the trajectory could have visited. In an experimental study, we show that our method is utility-preserving and protects sensitive locations reliably even in sparsely built environments. As it can process each trajectory independently, individuals may also use our mechanism to enhance their privacy before publishing their trajectories.

The visualization of spatio-temporal data helps researchers understand global processes such as animal migration. In particular, interactively restricting the data to different time windows reveals new insights into the short-term and long-term changes of the research data. Inspired by this use case, we consider the visualization of point data annotated with time stamps. We pick up classical, grid-based density maps as the underlying visualization technique and enhance them with an efficient data structure for arbitrarily specified time-window queries. The running time of the queries is logarithmic in the total number of points and linear in the number of actually colored cells. In experiments on real-world data we show that the data structure answers time-window queries within milliseconds, which supports the interactive exploration of large point sets. Further, the data structure can be used to visualize additional decision problems, e.g., it can answer whether the sum or maximum of additional weights given with the points exceed a certain threshold. We have defined the data structure general enough to also support multiple thresholds expressed by different colors.

The interactive exploration of data requires data structures that can be repeatedly queried to obtain simple visualizations of parts of the data. We consider the scenario that the data is a set of points each associated with a time stamp and that the result of each query is visualized by an α-shape, which generalizes the concept of convex hulls. Instead of computing each shape independently, we suggest and analyze a simple data structure that aggregates the α-shapes of all possible queries. Once the data structure is built, it particularly allows us to query single α-shapes without retrieving the actual (possibly large) point set and thus to rapidly produce small previews of the queried data. We discuss the data structure for the original α-shapes as well as for a schematized version of α-shapes, which further simplifies the visualization. We evaluate the data structure on real-world data. The experiments indicate linear memory consumption with respect to the number of points, which makes the data structure applicable in practice, although the size is quadratic for a theoretic worst case example.

Finding a shortest path between two nodes in a graph is a well-studied problem whose applicability in practice crucially relies on the choice of the applied cost function. Especially, for the key application of vehicle routing the cost function may consist of more than one optimization criterion (e.g., distance, travel time, etc.). Finding a good balance between these criteria is a challenging and essential task. We present an approach that learns that balance from existing GPS-tracks. The core of our approach is to find a balance factor α for a given set of GPS-tracks such that the tracks can be decomposed into a minimum number of optimal paths with respect to α.

In a connected weighted graph, consider deleting the edges one at a time, in some order, such that after every deletion the remaining edges are still connected. We study the problem of finding such a deletion sequence that maximizes the sum of the weights of the edges in all the distinct graphs generated: the weight of an edge is counted in every graph that it is in. This effectively asks for the high-weight edges to remain in the graph as long as possible, subject to connectivity. We apply this to road network generalization in order to generate a sequence of successively more generalized maps of a road network so that these maps go well together, instead of considering each level of generalization independently. In particular, we look at the problem of making a road segment selection that is consistent across zoom levels.

We consider the problem of labeling linear objects (such as streets) in interactive maps where the user can pan, zoom, and rotate continuously. Our labels contain text (such as street names). They are embedded into the objects they label, i.e., they follow the curvature of the objects, they do not move with respect to the map background, but they scale in order to maintain constant size on the screen. To the best of our knowledge, this is the first work that deals with curved labels in interactive maps.

We present a new algorithm that enlarges a focus region in a given network map without removing non-focus (i.e., context) network parts from the map or changing the map’s size. In cartography, this problem is usually tackled with fish-eye projections, which, however, introduce severe distortion. Our new algorithm minimizes distortion and, with respect to this objective, produces results of similar quality compared to an existing algorithm. In contrast to the existing algorithm, the new algorithm achieves real-time performance that allows its application in interactive systems. We target applications where a user sets a focus by brushing parts of the network or the focus region is defined as the neighborhood of a moving user.A crucial feature of the algorithm is its capability of avoiding unwanted edge crossings. Basically, we first solve a least-squares optimization problem without constraints for avoiding edge crossings. The solution we find is then used to identify a small set of constraints needed for a crossing-free solution and, beyond this, allows us to start an animation enlarging the focus region before the final, crossing-free solution is found. Moreover, memorizing the non-crossing constraints from an initial run of the algorithm allows us to achieve a better runtime on any further run – assuming that the focus region does not move too much between two consecutive runs. As we show with experiments on real-world data, this enables response times well below 1 second.

We present an algorithm for schematized focus maps. Focus maps integrate a high detailed, enlarged focus region continuously in a given base map. Recent methods integrate both with such low distortion that the focus region becomes hard to identify. We combine focus maps with partial schematization to display distortion of the context and to emphasize the focus region. Schematization visually conveys geographical accuracy, while not increasing map complexity. We extend the focus-map algorithm to incorporate geometric proximity relationships and show how to combine focus maps with schematization in order to cater to different use cases.

We consider the problem of matching a GPS trajectory with a road data set in which some roads are missing. To solve this problem, we extend a map-matching algorithm by Newson and Krumm (Proc. ACM GIS 2009, pp. 336--343) that is based on a hidden Markov model and a discrete set of candidate matches for each point of the trajectory. We introduce an additional off-road candidate for each point of the trajectory. The output path becomes determined by selecting one candidate for each point of the trajectory and connecting the selected candidates via shortest paths, which preferably lie in the road network but, if off-road candidates become selected, may also include off-road sections. We discuss experiments with GPS tracks of pedestrians.

Boundary labeling deals with placing annotations for objects in an image on the boundary of that image. This problem occurs frequently in situations where placing labels directly in the image is impossible or produces too much visual clutter. Previous algorithmic results for boundary labeling consider a single layer of labels along some or all sides of a rectangular image. If, however, the number of labels is large or labels are too long, multiple layers of labels are needed.

We present an optimization approach to simplify sets of building footprints represented as polygons. We simplify each polygonal ring by selecting a subsequence of its original edges; the vertices of the simplified ring are defined by intersections of consecutive (and possibly extended) edges in the selected sequence. Our aim is to minimize the number of all output edges subject to a user-defined error tolerance. Since we earlier showed that the problem is NP-hard when requiring non-intersecting simple polygons as output, we cannot hope for an efficient, exact algorithm. Therefore, we present an efficient algorithm for a relaxed problem and an integer program (IP) that allows us to solve the original problem with existing software. Our IP is large, since it has O(m6) constraints, where m is the number of input edges. In order to keep the running time small, we first consider a subset of only O(m) constraints. The choice of the constraints ensures some basic properties of the solution. Constraints that were neglected are added during optimization whenever they become violated by a new solution encountered. Using this approach we simplified a set of 144 buildings with a total of 2056 edges in 4.1 seconds on a standard desktop PC; the simplified building set contained 762 edges. During optimization, the number of constraints increased by a mere 13%. We also show how to apply cartographic quality measures in our method and discuss their effects on examples.

Topographic databases normally contain areas of different land cover classes, commonly defining a planar partition, that is, gaps and overlaps are not allowed. When reducing the scale of such a database, some areas become too small for representation and need to be aggregated. This unintentionally but unavoidably results in changes of classes. In this article we present an optimisation method for the aggregation problem. This method aims to minimise changes of classes and to create compact shapes, subject to hard constraints ensuring aggregates of sufficient size for the target scale. To quantify class changes we apply a semantic distance measure. We give a graph theoretical problem formulation and prove that the problem is NP-hard, meaning that we cannot hope to find an efficient algorithm. Instead, we present a solution by mixed-integer programming that can be used to optimally solve small instances with existing optimisation software. In order to process large datasets, we introduce specialised heuristics that allow certain variables to be eliminated in advance and a problem instance to be decomposed into independent sub-instances. We tested our method for a dataset of the official German topographic database ATKIS with input scale 1:50,000 and output scale 1:250,000. For small instances, we compare results of this approach with optimal solutions that were obtained without heuristics. We compare results for large instances with those of an existing iterative algorithm and an alternative optimisation approach by simulated annealing. These tests allow us to conclude that, with the defined heuristics, our optimisation method yields high-quality results for large datasets in modest time.

We consider the problem of localizing a moving vehicle based on landmarks that were detected with a vehicle-mounted sensor. Landmarks are represented as points; correspondences of these points with the ones in a reference database are searched based on their geometric configurations. More specifically, we triangulate the landmark points and we match the obtained triangles with triangles in a reference database according to their geometric similarity. We maximize the number of triangle matches while considering the topological relations between different triangles, for example, if two triangles share an edge then the corresponding reference triangles must share an edge. Our method exploits that the observed points typically form a certain configuration: They appear at a limited distance from the vehicle's trajectory, thus the typical point pattern has a large extent in the driving direction and a relatively small lateral extent. This characteristic allows us to triangulate the observed point set such that we obtain a triangle strip (a sequence of triangles) in which each two consecutive triangles share one edge and each triangle connects three points that are relatively close to each other, that is, the triangle strip appropriately defines a neighborhood relationship for the landmarks. The adjacency graph of the triangles becomes a path; this allows for an efficient solution of our matching problem by dynamic programming. We present results of our method with data acquired with a mobile laser scanning system. The landmarks are objects of cylindric shape, for example, poles of traffic signs, which can be easily detected with the employed sensor. We tested the method with respect to its running time and its robustness when imposing different types of errors on the data. In particular, we tested the effect of non-rigid distortions of the observed point set, which are typically encountered during dead reckoning. Our matching approach copes well with such errors since it is based on local similarity measures of triangles, that is, we do not assume that a global non-rigid transformation between the observed point set and the reference point set exists.

We present a novel method for the automatic generalization of land cover maps. A land cover map is composed of areas that collectively form a tessellation of the plane and each area is assigned to a land cover class such as lake, forest, or settlement. Our method aggregates areas into contiguous regions of equal class and of size greater than a user-defined threshold. To achieve this goal, some areas need to be enlarged at the expense of others. Given function that defines costs for the transformation between pairs of classes, our method guarantees to return a solution of minimal total cost. The method is based on a mixed integer program (MIP). To process maps with more than 50 areas, heuristics are introduced that lead to an alternative MIP formulation. The effects of the heuristics on the obtained solution and the computation time are discussed. The methods were tested using real data from the official German topographic data set (ATKIS) at scales 1:50.000 and 1:250.000.