This repository contains benchmark instances for (s,t)-max-flow/min-cut, which were submitted to the 13th DIMACS Implementation Challenge. The instances are derived from the bicriteria polygon aggregation problem, which is studied in the following publications: Bicriteria Shapes: Hierarchical Grouping and Aggregation of Polygons with an Efficient Graph-Cut Approach. Peter Rottmann, Anne Driemel, Herman Haverkort, Heiko Röglin, Jan-Henrik Haunert. In: ACM Transactions on Spatial Algorithms and Systems, vol. 11(1), ACM, pages 3:1--3:23, 2025. A Simpler Approach for Monotone Parametric Minimum Cut: Finding the Breakpoints in Order. Arne Beines, Michael Kaibel, Philip Mayer, Petra Mutzel, Jonas Sauer. In: Proceedings of the 27th Workshop on Algorithm Engineering and Experiments (ALENEX'25), SIAM, pages 29--41, 2025. Bicriteria Polygon Aggregation with Arbitrary Shapes. Lotte Blank, David Eppstein, Jan-Henrik Haunert, Herman Haverkort, Benedikt Kolbe, Philip Mayer, Petra Mutzel, Alexander Naumann, Jonas Sauer. To appear in: Proceedings of the 34th Annual European Symposium on Algorithms (ESA'26), Leibniz International Proceedings in Informatics, 2026. Background These instances are derived from a real-world application: polygon aggregation for map simplification. Given is a set $P$ of building footprints, represented as 2D polygons. The objective is to find a set $S$ of interior-disjoint representative regions, such that each polygon in $P$ is fully contained in a region of $S$. We are interested in a solution that minimizes the objective function $g_\alpha(S) = A(S) + \alpha \cdot P(S)$, where $A(S)$ and $P(S)$ are the total area and perimeter of the regions in $S$, respectively. The parameter $\alpha$ controls the trade-off between faithfulness to the input (represented by the area) and shape simplicity (represented by the perimeter). In a cartographic application, it can be thought of as the "zoom factor" -- the further we zoom out, the simpler we want the shapes to become. We distinguish between two variants of the problem, both for a fixed choice of $\alpha$: Subdivision-based: A subdivision $D$ of the plane (e.g., a constrained Delaunay triangulation) is supplied in advance, such that each polygon in $P$ appears as a cell of $D$. The solution must be constructed by selecting cells from $D$ to add to $P$. The problem is solved via a transformation to (s,t)-min-cut on an augmented geometric dual of $D$ (see any of the papers listed above for details). Unrestricted: No restrictions are made regarding the shape of $S$ -- the only conditions are that $P$ must be covered and that the objective function $g_\alpha(S)$ is minimized. Blank et al. show that in this variant, the polygons are connected by circular arcs of radius $\alpha$ that fulfill several other conditions. The arcs are chosen from a set of $O(n^2)$ candidates. The problem can then be solved optimally via a transformation to the subdivision-based case, where the subdivision $D$ is created by superimposing all $O(n^2)$ arcs. This yields a solution in polynomial time, although the subdivision is much more complex than the constrained Delaunay triangulation. The resulting instances have some similarities with grid-based computer vision max-flow instances, which are built using a similar geometric-dual construction: They are sparse and have short (s,t)-paths. However, unlike typical vision instances, they do not have a regular structure because they are derived from human settlement areas. Consequently, although all nodes (except for s and t) have low degrees, the degrees are not entirely uniform. For the unrestricted variant, the graph is highly detailed because it is derived from a geometric intersection process between many circular arcs. As a side note, a parametric version of the problem, where $\alpha$ is not fixed, has also been studied. Here, the objective is to find an optimal solution for every possible value of $\alpha$. Beines et al. show that, with an equivalent reformulation of the objective function $g_\alpha$, this is a monotone parametric min-cut problem. The instances in this dataset are not parametric, but parametric instances can be found here. Contents The dataset is split into two groups, depending on how the subdivision was built: triangulations: Using a constrained Delaunay triangulation, as proposed by Rottmann et al. The instances are cities of varying sizes (Bonn, Cologne, Berlin, Miami) and the entire German state of Saarland. For each instance, there are five copies, with the different $\alpha$ values 100, 500, 1000, 5000, and 25000. Note that the graph structure is the same for all copies; only the weights are different. arcs: Using the geometric intersection of the candidate arcs, as proposed by Blank et al. for the unrestricted variant. The instances represent the towns of Ahrem, Edendorf, Friesheim and Gerolstein in the German state of North Rhine-Westphalia. For each instance, there are four copies, with the different $\alpha$ values 100, 500, 1000, 5000. Note that for this variant, the graph size increases dramatically with $\alpha$. The arc capacities represent a weighted tradeoff between area and perimeter, measured in square decimeters (dm^2) and rounded to the nearest integer. The $\alpha$ parameter is also measured in decimeters. In the arcs instances, this corresponds to the radii of the circular arcs from which the subdivision is formed, e.g., $\alpha=5000$ represents arcs with radii of 500m. Data Sources Ahrem, Friesheim, Edendorf, Gerolstein, Bonn, Cologne: OpenStreetMap data from Geofabrik Saarland: OpenStreetMap data from Geofabrik Berlin, Miami: GHS-OBAT project Format The files follow the format from the first DIMACS implementation challenge. This is a text format in which each line is prefixed with a character that specifies the type of line. Lines starting with c are comments and should be ignored. The first non-comment line is the problem line: p max NODES ARCS Here, max is the problem type (max-flow/min-cut), NODES is the number of nodes in the network, and ARCS is the number of directed arcs. This is followed by two node descriptor lines:n IDT tn IDS s Here, IDT is the id of the sink node and IDS is the id of the source node. Note that in this format, node ids start at 1. Finally, there is an arc descriptor line for every directed arc in the network: a SRC DST C This specifies an arc from node SRC to DST with capacity C. Capacities with values of int32_max or more should be interpreted as infinite. Note that the format does not require that a reverse arc exists for every directed arc. If reverse arcs are required by your algorithm, you must ensure that missing arcs are added with capacity 0. Credits and Contact This dataset was created by two research groups at the University of Bonn: the geoinformation group headed by Prof. Dr. Jan-Henrik Haunert and the Computational Analytics group headed by Prof. Dr. Petra Mutzel. It is released under the MIT license. When using it, please cite the publications listed above. If you want to report problems or give feedback on the dataset, please contact Jonas Sauer ([email protected]).

Regionalization is a fundamental task in spatial analysis that seeks to partition a larger area - such as a country - into smaller regions that are homogeneous with respect to a given attribute. A popular model for regionalization is the p-regions problem, in which regions are formed by grouping the areas of an input planar subdivision. Given the subdivision’s adjacency graph G and pairwise dissimilarities between vertices, the goal is to partition G into a fixed number p of connected subgraphs, such as to minimize the sum of dissimilarities over all vertex pairs in the same subgraph. The problem is NP-hard and even small instances are difficult to solve to provable optimality. In this paper, we present the new ILP model ER-S for the p-regions problem, exploiting a connection between the p-regions objective and the k-partitioning problem. Furthermore, we strengthen the known ILP model Tree with a new type of subtour elimination inequality specific to the p-regions problem. Combining ER-S and the strengthened version of Tree yields the model ER-S-Tree, which dominates the state-of-the-art models in polyhedral strength. This theoretical advantage is reflected in its superior performance in our experimental evaluation. In particular, the new models ER-S and ER-S-Tree enable the solution of problem instances for major European countries that were previously intractable.

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.

User interfaces for inspecting spatio-temporal events often allow their users to filter the events by specifying a time window with a time slider. We consider the case that filtered events are visualized on a map using textual or iconic labels. However, to ensure a clear visualization, not all filtered events are annotated with a label. We present algorithms for setting up a data structure that encodes for every possible time window the set of displayed labels. Our algorithms ensure that the displayed labels never overlap and guarantee the stability of the labeling during certain basic interactions with the time slider. Assuming that the labels have different priorities (weights), we aim to maximize the weight of the displayed labels integrated over all possible time windows. As basic interactions, we consider moving the entire time window, symmetrically scaling it, and dragging one of its endpoints. We consider two stability requirements: (1) during a basic interaction, a label should appear and disappear at most once; (2) if a label is displayed for a time window $Q$Q, then it is also displayed for all the time windows contained in $Q$Q and that contain its timestamp. We prove that finding an optimal solution is NP-hard and propose efficient constant-factor approximation algorithms for unit-square and unit-disk labels, as well as a fast greedy heuristic for arbitrarily shaped labels. In experiments on real-world data, we compare the non-exact algorithms with an exact approach through integer linear programming.

Euler diagrams are an intuitive and popular method to visualize set-based data. In an Euler diagram, each set is represented as a closed curve, and set intersections are shown by curve overlaps. However, Euler diagrams are not visually scalable and automatic layout techniques struggle to display real-world data sets in a comprehensible way. Prior state-of-the-art approaches can embed Euler diagrams by splitting a closed curve into multiple curves so that a set is represented by multiple disconnected enclosed areas. In addition, these methods typically result in multiple curve segments being drawn concurrently. Both of these features significantly impede understanding. In this paper, we present a new and scalable method for embedding Euler diagrams using set merges. Our approach simplifies the underlying data to ensure that each set is represented by a single, connected enclosed area and that the diagram is drawn without curve concurrency, leading to wellformed and understandable Euler diagrams.

Abstract Can a given set system be drawn as an Euler diagram? We present the first method that correctly decides this question for arbitrary set systems if the Euler diagram is required to represent each set with a single connected region. If the answer is yes, our method constructs an Euler diagram. If the answer is no, our method yields an Euler diagram for a simplified version of the set system, where a minimum number of set elements have been removed. Further, we integrate known wellformedness criteria for Euler diagrams as additional optimization objectives into our method. Our focus lies on the computation of a planar graph that is embedded in the plane to serve as the dual graph of the Euler diagram. Since even a basic version of this problem is known to be NP‐hard, we choose an approach based on integer linear programming (ILP), which allows us to compute optimal solutions with existing mathematical solvers. For this, we draw upon previous research on computing planar supports of hypergraphs and adapt existing ILP building blocks for contiguity‐constrained spatial unit allocation and the maximum planar subgraph problem. To generate Euler diagrams for large set systems, for which the proposed simplification through element removal becomes indispensable, we also present an efficient heuristic. We report on experiments with data from MovieDB and Twitter. Over all examples, including 850 non‐trivial instances, our exact optimization method failed only for one set system to find a solution without removing a set element. However, with the removal of only a few set elements, the Euler diagrams can be substantially improved with respect to our wellformedness criteria.

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.

Visualizing sets of elements and their relations is an important research area in information visualization. In this paper, we present MosaicSets: a novel approach to create Euler-like diagrams from non-spatial set systems such that each element occupies one cell of a regular hexagonal or square grid. The main challenge is to find an assignment of the elements to the grid cells such that each set constitutes a contiguous region. As use case, we consider the research groups of a university faculty as elements, and the departments and joint research projects as sets. We aim at finding a suitable mapping between the research groups and the grid cells such that the department structure forms a base map layout. Our objectives are to optimize both the compactness of the entirety of all cells and of each set by itself. We show that computing the mapping is NP-hard. However, using integer linear programming we can solve real-world instances optimally within a few seconds. Moreover, we propose a relaxation of the contiguity requirement to visualize otherwise non-embeddable set systems. We present and discuss different rendering styles for the set overlays. Based on a case study with real-world data, our evaluation comprises quantitative measures as well as expert interviews.

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.

Abstract In geographic data analysis, one is often given point data of different categories (such as facilities of a university categorized by department). Drawing upon recent research on set visualization, we want to visualize category membership by connecting points of the same category with visual links. Existing approaches that follow this path usually insist on connecting all members of a category, which may lead to many crossings and visual clutter. We propose an approach that avoids crossings between connections of different categories completely. Instead of connecting all data points of the same category, we subdivide categories into smaller, local clusters where needed. We do a case study comparing the legibility of drawings produced by our approach and those by existing approaches. In our problem formulation, we are additionally given a graph G on the data points whose edges express some sort of proximity. Our aim is to find a subgraph G′ of G with the following properties: (i) edges connect only data points of the same category, (ii) no two edges cross, and (iii) the number of connected components (clusters) is minimized. We then visualize the clusters in G′. For arbitrary graphs, the resulting optimization problem, Cluster Minimization, is NP‐hard (even to approximate). Therefore, we introduce two heuristics. We do an extensive benchmark test on real‐world data. Comparisons with exact solutions indicate that our heuristics do astonishing well for certain relative‐neighborhood graphs.

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 α.

Abstract Suppose a user located at a certain vertex in a road network wants to plan a route using a wayfinding map. The user's exact destination may be irrelevant for planning most of the route, because many destinations will be equivalent in the sense that they allow the user to choose almost the same paths. We propose a method to find such groups of destinations automatically and to contract the resulting clusters in a detailed map to achieve a simplified visualization. We model the problem as a clustering problem in rooted, edge‐weighted trees. Two vertices are allowed to be in the same cluster if and only if they share at least a given fraction of their path to the root. We analyze some properties of these clusterings and give a linear‐time algorithm to compute the minimum‐cardinality clustering. This algorithm may have various other applications in network visualization and graph drawing, but in this paper we apply it specifically to focus‐and‐context map generalization. When contracting shortest‐path trees in a geographic network, the computed clustering additionally provides a constant‐factor bound on the detour that results from routing using the generalized network instead of the full network. This is a desirable property for wayfinding maps.

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.

Scatter plots are diagrams that visualize two-dimensional data as sets of points in the plane. They allow users to detect correlations and clusters in the data. Whether or not a user can accomplish these tasks highly depends on the aspect ratio selected for the plot, i.e., the ratio between the horizontal and the vertical extent of the diagram. We argue that an aspect ratio is good if the Delaunay triangulation of the scatter plot at this aspect ratio has some nice geometric property, e.g., a large minimum angle or a small total edge length. More precisely, we consider the following optimization problem. Given a set Q of points in the plane, find a scale factor s such that scaling the x-coordinates of the points in Q by s and the y-coordinates by 1=s yields a point set P(s) that optimizes a property of the Delaunay triangulation of P(s), over all choices of s. We present an algorithm that solves this problem efficiently and demonstrate its usefulness on real-world instances. Moreover, we discuss an empirical test in which we asked 64 participants to choose the aspect ratios of 18 scatter plots. We tested six different quality measures that our algorithm can optimize. In conclusion, minimizing the total edge length and minimizing what we call the 'uncompactness' of the triangles of the Delaunay triangulation yielded the aspect ratios that were most similar to those chosen by the participants in the test.

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.

In this paper, we investigate the problem of labeling point sites in focus regions of maps or diagrams. This problem occurs, for example, when the user of a mapping service wants to see the names of restaurants or other POIs in a crowded downtown area but keep the overview over a larger area. Our approach is to place the labels at the boundary of the focus region and connect each site with its label by a linear connection, which is called a leader. In this way, we move labels from the focus region to the less valuable context region surrounding it. In order to make the leader layout well readable, we present algorithms that rule out crossings between leaders and optimize other characteristics such as total leader length and distance between labels. This yields a new variant of the boundary labeling problem, which has been studied in the literature. Other than in traditional boundary labeling, where leaders are usually schematized polylines, we focus on leaders that are either straight-line segments or Bezier curves. Further, we present algorithms that, given the sites, find a position of the focus region that optimizes the above characteristics. We also consider a variant of the problem where we have more sites than space for labels. In this situation, we assume that the sites are prioritized by the user. Alternatively, we take a new facility-location perspective which yields a clustering of the sites. We label one representative of each cluster. If the user wishes, we apply our approach to the sites within a cluster, giving details on demand.

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.

Mobile users of maps typically need detailed information about their surroundings plus some context information about remote places. In order to avoid that the map partly gets too dense, cartographers have designed mapping functions that enlarge a user-defined focus region--such functions are sometimes called fish-eye projections. The extra map space occupied by the enlarged focus region is compensated by distorting other parts of the map. We argue that, in a map showing a network of roads relevant to the user, distortion should preferably take place in those areas where the network is sparse. Therefore, we do not apply a predefined mapping function. Instead, we consider the road network as a graph whose edges are the road segments. We compute a new spatial mapping with a graph-based optimization approach, minimizing the square sum of distortions at edges. Our optimization method is based on a convex quadratic program (CQP); CQPs can be solved in polynomial time. Important requirements on the output map are expressed as linear inequalities. In particular, we show how to forbid edge crossings. We have implemented our method in a prototype tool. For instances of different sizes, our method generated output maps that were far less distorted than those generated with a predefined fish-eye projection. Future work is needed to automate the selection of roads relevant to the user. Furthermore, we aim at fast heuristics for application in real-time systems.

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.