Axel Forsch, Johannes Oehrlein, Benjamin Niedermann, and Jan-Henrik Haunert. Inferring routing preferences from user-generated trajectories using a compression criterion. Journal of Spatial Information Science, 0(0):0, 2023. Accepted for publication on 15 Mar 2023.
Annika Bonerath, Jan-Henrik Haunert, Joseph S.B. Mitchell, and Benjamin Niedermann. Shortcut hulls: vertex-restricted outer simplifications of polygons. Computational Geometry Theory and Applications, :101983, 2023.
Let P be a polygon and C a set of shortcuts, where each shortcut is a directed straight-line segment connecting two vertices of P. A shortcut hull of P is another polygon that encloses P and whose oriented boundary is composed of elements from C. We require P and the output shortcut hull to be weakly simple polygons, which we define as a generalization of simple polygons. Shortcut hulls find their application in cartography, where a common task is to compute simplified representations of area features. We aim at a shortcut hull that has a small area and a small perimeter. Our optimization objective is to minimize a convex combination of these two criteria. If no holes in the shortcut hull are allowed, the problem admits a straight-forward solution via computation of shortest paths. For the more challenging case in which the shortcut hull may contain holes, we present a polynomial-time algorithm that is based on computing a constrained, weighted triangulation of the input polygon's exterior. We use this problem as a starting point for investigating further variants, e.g., restricting the number of edges or bends. We demonstrate that shortcut hulls can be used for the schematization of polygons.
Y. Dehbi, J. Knechtel, B. Niedermann, and J.-H. Haunert. Incremental constraint-based reasoning for estimating as-built electric line routing in buildings. Automation in Construction, 143:104571, 2022.
This article addresses the augmentation of existing building models by a-priori not observable structures such as electric installations. The aim is to unambiguously determine an electric network in an incremental manner with a minimum number of local measurements, e.g. using wire detectors, by suggesting the next measurement. Different reasoning strategies, e.g. utilizing graph-theoretical algorithms, have been presented and tested based on a hypothesis which is generated using Mixed Integer Linear Programming (MILP) while incorporating standards regarding the installation of electric wiring and findings from previous measurements. The presented method has been successfully applied on simulated and real-world buildings, it saves up to 80% of the necessary measurements compared to an exhaustive verification of the whole existing electric network, and paves the way for efficiently extending existing models, e.g. GIS models, with information on hidden utilities. This opens up new opportunities to model further infrastructures, e.g. water pipes, in future research.
Annika Bonerath, Jan-Henrik Haunert, Joseph S. B. Mitchell, and Benjamin Niedermann. Shortcut hulls: vertex-restricted outer simplifications of polygons. In Meng He, and Don Sheehy, editors. Proceedings of the 33rd Canadian Conference on Computational Geometry, pages 12-23. 2021.
Let P be a crossing-free polygon and C a set of shortcuts, where each shortcut is a directed straight-line segment connecting two vertices of P. A shortcut hull of P is another crossing-free polygon that encloses P and whose oriented boundary is composed of elements from C. Shortcut hulls find their application in geo-related problems such as the simplification of contour lines. We aim at a shortcut hull that linearly balances the enclosed area and perimeter. If no holes in the shortcut hull are allowed, the problem admits a straight-forward solution via shortest paths. For the more challenging case that the shortcut hull may contain holes, we present a polynomial-time algorithm that is based on computing a constrained, weighted triangulation of the input polygon’s exterior. We use this problem as a starting point for investigating further variants, e.g., restricting the number of edges or bends. We demonstrate that shortcut hulls can be used for drawing the rough extent of point sets as well as for the schematization of polygons.
S. Gedicke, A. Bonerath, B. Niedermann, and J.-H. Haunert. Zoomless maps: external labeling methods for the interactive exploration of dense point sets at a fixed map scale. IEEE Transactions on Visualization and Computer Graphics, 27(2):1247-1256, 2021. https://youtu.be/IuMhk8jp54c
Visualizing spatial data on small-screen devices such as smartphones and smartwatches poses new challenges in computational cartography. The current interfaces for map exploration require their users to zoom in and out frequently. Indeed, zooming and panning are tools suitable for choosing the map extent corresponding to an area of interest. They are not as suitable, however, for resolving the graphical clutter caused by a high feature density since zooming in to a large map scale leads to a loss of context. Therefore, in this paper, we present new external labeling methods that allow a user to navigate through dense sets of points of interest while keeping the current map extent fixed. We provide a unified model, in which labels are placed at the boundary of the map and visually associated with the corresponding features via connecting lines, which are called leaders. Since the screen space is limited, labeling all features at the same time is impractical. Therefore, at any time, we label a subset of the features. We offer interaction techniques to change the current selection of features systematically and, thus, give the user access to all features. We distinguish three methods, which allow the user either to slide the labels along the bottom side of the map or to browse the labels based on pages or stacks. We present a generic algorithmic framework that provides us with the possibility of expressing the different variants of interaction techniques as optimization problems in a unified way. We propose both exact algorithms and fast and simple heuristics that solve the optimization problems taking into account different criteria such as the ranking of the labels, the total leader length as well as the distance between leaders. In experiments on real-world data we evaluate these algorithms and discuss the three variants with respect to their strengths and weaknesses proving the flexibility of the presented algorithmic framework.
Axel Forsch, Youness Dehbi, Benjamin Niedermann, Johannes Oehrlein, Peter Rottmann, and Jan-Henrik Haunert. Multimodal travel-time maps with formally correct and schematic isochrones. Transactions in GIS, 25(6):3233-3256, 2021.
The automatic generation of travel-time maps is a prerequisite for many fields of application such as tourist assistance and spatial decision support systems. The task is to determine outlines of zones that are reachable from a user's location in a given amount of time. In this work, we focus on travel-time maps with a formally guaranteed separation property in the sense that a zone exactly contains the part of the road network that is reachable within a pre-defined time from a given starting point and start time. In contrast to other automated methods, our approach generates schematized travel-time maps that reduce the visual complexity by representing each zone by an octilinear polygon. We aim at octilinear polygons with a small number of bends to further optimize the legibility of the map. The reachable parts of the road network are determined by the integration of timetable information for different modes of public transportation and pedestrian walkways based on a multi-modal time-expanded network. Moreover, the generated travel-time maps visualize multiple travel times using a map overlay of different time zones. In experiments on real-world data we compare our schematic visualizations to travel-time maps created with other visualization techniques.
S. Gedicke, A. Jabrayilov, B. Niedermann, P. Mutzel, and J.-H. Haunert. Point feature label placement for multi-page maps on small-screen devices. Computers & Graphics, 100:66-80, 2021.
Map applications on mobile devices such as smartphones and smartwatches have become ubiquitous. When visualizing spatial data on such small-screen devices, one major challenge is annotating the data with labels (e.g., small icons). The restricted space requires new visualization techniques as established strategies, such as maximizing the number of placed labels, easily lead to the omission of information. We propose an approach that distributes all labels contained in a temporarily fixed map section on multiple pages. Applying interaction techniques for navigating through the pages, a user can access all information both without any overlapping labels and without the need for zooming. We propose a method with two phases; a pre-processing phase and a query phase. We use an optimization approach to pre-compute labelings on the level of a whole city and provide the on-demand querying of individual labelings at a more local level. Our approach provides a consistent label-page assignment, meaning that labels do not appear and disappear when the user pans the map. Further, our model provides quick access to important information and a spatially balanced distribution of labels on pages. In experiments on real-world data we analyze different parameter settings and show that our model yields high-quality labelings.
A. Bonerath, B. Niedermann, J. Diederich, Y. Orgeig, J. Oehrlein, and J.-H. Haunert. A time-windowed data structure for spatial density maps. In Proc. 28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL '20), pages 15-24. 2020.
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.
B. Niedermann, and I. Rutter. An integer-linear program for bend-minimization in ortho-radial drawings. In David Auber, and Pavel Valtr, editors, Lecture Notes in Computer Science. Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD'20). Springer, 2020.
An ortho-radial grid is described by concentric circles and straight-line spokes emanating from the circles' center. An ortho-radial drawing is the analog of an orthogonal drawing on an ortho-radial grid. Such a drawing has an unbounded outer face and a central face that contains the origin. Building on the notion of an ortho-radial representation (Barth et al., SoCG, 2017), we describe an integer-linear program (ILP) for computing bend-free ortho-radial representations with a given embedding and fixed outer and central face. Using the ILP as a building block, we introduce a pruning technique to compute bend-optimal ortho-radial drawings with a given embedding and a fixed outer face, but freely choosable central face. Our experiments show that, in comparison with orthogonal drawings using the same embedding and the same outer face, the use of ortho-radial drawings reduces the number of bends by 43.8% on average. Further, our approach allows us to compute ortho-radial drawings of embedded graphs such as the metro system of Beijing or London within seconds.
H.-Y. Wu, B. Niedermann, S. Takahashi, M. J. Roberts, and M. Nöllenburg. A survey on transit map layout - from design, machine, and human perspectives. Computer Graphics Forum, 39(3), 2020.
Transit maps are designed to present information for using public transportation systems, such as urban railways. Creating a transit map is a time-consuming process, which requires iterative information selection, layout design, and usability validation, and thus maps cannot easily be customised or updated frequently. To improve this, scientists investigate fully- or semi-automatic techniques in order to produce high quality transit maps using computers and further examine their corresponding usability. Nonetheless, the quality gap between manually-drawn maps and machine-generated maps is still large. To elaborate the current research status, this state-of-the-art report provides an overview of the transit map generation process, primarily from Design, Machine, and Human perspectives. A systematic categorisation is introduced to describe the design pipeline, and an extensive analysis of perspectives is conducted to support the proposed taxonomy. We conclude this survey with a discussion on the current research status, open challenges, and future directions.
A. Gemsa, B. Niedermann, and M. Nöllenburg. A unified model and algorithms for temporal map labeling. Algorithmica, 82:2702-2736, 2020.
We consider map labeling for the case that a map undergoes a sequence of operations such as rotation, zoom and translation over a specified time span. We unify and generalize several previous models for dynamic map labeling into one versatile and flexible model. In contrast to previous research, we completely abstract from the particular operations and express the labeling problem as a set of time intervals representing the labels’ presences, activities and conflicts. One of the model’s strength is manifested in its simplicity and broad range of applications. In particular, it supports label selection both for map features with fixed position as well as for moving entities (e.g., for tracking vehicles in logistics or air traffic control). We study the active range maximization problem in this model. We prove that the problem is NP-complete and W-hard, and present constant-factor approximation algorithms. In the restricted, yet practically relevant case that no more than k labels can be active at any time, we give polynomial-time algorithms as well as constant-factor approximation algorithms.
A. Bonerath, J.-H. Haunert, and B. Niedermann. Tight rectilinear hulls of simple polygons. In Proceedings of the 36th European Workshop on Computational Geometry (EuroCG'20). 2020. trailer: https://youtu.be/GZTS5fs0FG4, presentation: https://youtu.be/B392e75WK2U
A polygon is called C-oriented if the orientations of all its edges stem from a pre-defined set C. The schematization of a polygon is then a C-oriented polygon that describes and simplifies the shape of the input polygon with respect to given hard and soft constraints. We study the case that the C-oriented polygon needs to contain the input polygon such that it is tight in the sense that it cannot be shrunk without starting to overlap with the input polygon; we call this a tight C-hull of the polygon. We restrict the tight C-hull to be a simple polygon. We aim at a tight C-hull that optimally balances the number of bends, the total edge length and the enclosed area. For the case that both polygons are rectilinear, we present a dynamic-programming approach that yields such a tight hull in polynomial time. For arbitrary simple polygons we can use the same approach to obtain approximate tight rectilinear hulls.
A. Bonerath, J.-H. Haunert, and B. Niedermann. Dynamic aggregation of geo-objects for the interactive exploration of research data. In volume 29. Publikationen der Deutschen Gesellschaft für Photogrammetrie, Fernerkundung und Geoinformation e.V., DGPF Jahrestagung 2020, Stuttgart, Germany, pages 488-496. 2020.
In the context of research data management, the interactive exploration of data is a useful tool to make data findable and reusable. For exploring spatio- and temporal data we developed in a previously published work a data structure that provides the user with simple visualizations of the data for time window queries. We considered the data to be points in space each associated with a time stamp and we visualized it using \alpha-shapes, which generalize convex hulls. In general, time windowed data structures support time window queries for geometric shapes or more general problems from computational geometry such as counting and intersection problems. With this paper, we contribute a review of our previously published method in the context of time windowed data structures, which is a relatively new concept of computational geometry. In particular, we highlight the relevance of our work for a growing domain of research.
A. Gemsa, B. Niedermann, and M. Nöllenburg. Placing labels in road maps: algorithms and complexity. Algorithmica, 0(0):1-28, 2020. Online first.
A road map can be interpreted as a graph embedded in the plane, in which each vertex corresponds to a road junction and each edge to a particular road section. In this paper, we consider the computational cartographic problem to place non-overlapping road labels along the edges so that as many road sections as possible are identified by their name, i.e., covered by a label. We show that this is NP-hard in general, but the problem can be solved in cubic running time if the road map is an embedded tree with n vertices and constant maximum degree. This special case is not only of theoretical interest, but our algorithm in fact provides a very useful subroutine in exact or heuristic algorithms for labeling general road maps.
A. Corbin, B. Niedermann, A. Nothnagel, Haas R., and J.-H. Haunert. Combinatorial optimization applied to VLBI scheduling. Journal of Geodesy, 94(19):1-22, 2020.
Due to the advent of powerful solvers, today linear programming has seen many applications in production and routing. In this publication, we present mixed-integer linear programming as applied to scheduling geodetic very-long-baseline interferometry (VLBI) observations. The approach uses combinatorial optimization and formulates the scheduling task as a mixed-integer linear program. Within this new method, the schedule is considered as an entity containing all possible observations of an observing session at the same time, leading to a global optimum. In our example, the optimum is found by maximizing the sky coverage score. The sky coverage score is computed by a hierarchical partitioning of the local sky above each telescope into a number of cells. Each cell including at least one observation adds a certain gain to the score. The method is computationally expensive and this publication may be ahead of its time for large networks and large numbers of VLBI observations. However, considering that developments of solvers for combinatorial optimization are progressing rapidly and that computers increase in performance, the usefulness of this approach may come up again in some distant future. Nevertheless, readers may be prompted to look into these optimization methods already today seeing that they are available also in the geodetic literature. The validity of the concept and the applicability of the logic are demonstrated by evaluating test schedules for five 1-h, single-baseline Intensive VLBI sessions. Compared to schedules that were produced with the scheduling software sked, the number of observations per session is increased on average by three observations and the simulated precision of UT1-UTC is improved in four out of five cases (6 µs average improvement in quadrature). Moreover, a simplified and thus much faster version of the mixed-integer linear program has been developed for modern VLBI Global Observing System telescopes.
M. Bekos, B. Niedermann, and M. Nöllenburg. External labeling techniques: a taxonomy and survey. Computer Graphics Forum, 38(3):833-860, 2019.
Abstract External labeling is frequently used for annotating features in graphical displays and visualizations, such as technical illustrations, anatomical drawings, or maps, with textual information. Such a labeling connects features within an illustration by thin leader lines with their labels, which are placed in the empty space surrounding the image. Over the last twenty years, a large body of literature in diverse areas of computer science has been published that investigates many different aspects, models, and algorithms for automatically placing external labels for a given set of features. This state-of-the-art report introduces a first unified taxonomy for categorizing the different results in the literature and then presents a comprehensive survey of the state of the art, a sketch of the most relevant algorithmic techniques for external labeling algorithms, as well as a list of open research challenges in this multidisciplinary research field.
B. Niedermann, and J.-H. Haunert. Focus+context map labeling with optimized clutter reduction. International Journal of Cartography, 5(2-3):158-177, 2019. Special issue of 29th International Cartographic Conference (ICC'19)
Zooming is a basic operation that many digital maps support for exploring them interactively. Especially for maps on small-screen devices this is a helpful operation to uncover the user’s region of interest possibly hidden by labels, e.g., points of interest represented by icons. However, by scaling the map larger the user loses the context. As a consequent the user might need to repeatedly zoom in and out to explore the map step by step. We present an approach that reduces the necessity of zooming by providing the user with the possibility of displacing the labels of a circular focus region. To that end, we utilize techniques from focus+context maps implementing the displacement of the labels by fish-eye projections. The visual association between labels and their point features is established by connecting lines aggregated to bundles. Our approach particularly guarantees that labels move smoothly when the user continuously shifts the focus region, which reduces distracting flickering effects while exploring the map by panning the map view. Further, when the user stops moving the focus region, mathematical programming is applied to optimize positions of the displaced labels. In an evaluation on real-world data and synthetically generated data we show that our approach substantially increases the legibility of both the focus region and the displaced labels
B. Niedermann, I. Rutter, and M. Wolf. Efficient algorithms for ortho-radial graph drawing. In volume 129 of Leibniz International Proceedings in Informatics. Proc. 35th Annual ACM Symposium on Computational Geometry (SoCG '19). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.
Orthogonal drawings, i.e., embeddings of graphs into grids, are a classic topic in Graph Drawing. Often the goal is to find a drawing that minimizes the number of bends on the edges. A key ingredient for bend minimization algorithms is the existence of an orthogonal representation that allows to describe such drawings purely combinatorially by only listing the angles between the edges around each vertex and the directions of bends on the edges, but neglecting any kind of geometric information such as vertex coordinates or edge lengths. Barth et al. have established the existence of an analogous ortho-radial representation for ortho-radial drawings, which are embeddings into an ortho-radial grid, whose gridlines are concentric circles around the origin and straight-line spokes emanating from the origin but excluding the origin itself. While any orthogonal representation admits an orthogonal drawing, it is the circularity of the ortho-radial grid that makes the problem of characterizing valid ortho-radial representations all the more complex and interesting. Barth et al. prove such a characterization. However, the proof is existential and does not provide an efficient algorithm for testing whether a given ortho-radial representation is valid, let alone actually obtaining a drawing from an ortho-radial representation. In this paper we give quadratic-time algorithms for both of these tasks. They are based on a suitably constrained left-first DFS in planar graphs and several new insights on ortho-radial representations. Our validity check requires quadratic time, and a naive application of it would yield a quartic algorithm for constructing a drawing from a valid ortho-radial representation
L. Barth, A. Gemsa, B. Niedermann, and M. Nöllenburg. On the readability of leaders in boundary labeling. Information Visualization, 18(1):110-132, 2019.
External labeling deals with annotating features in images with labels that are placed outside of the image and are connected by curves (so-called leaders) to the corresponding features. While external labeling has been extensively investigated from a perspective of automatization, the research on its readability has been neglected. In this article, we present the first formal user study on the readability of leader types in boundary labeling, a special variant of external labeling that considers rectangular image contours. We consider the four most studied leader types (straight, L-shaped, diagonal, and S-shaped) with respect to their performance, that is, whether and how fast a viewer can assign a feature to its label and vice versa. We give a detailed analysis of the results regarding the readability of the four models and discuss their aesthetic qualities based on the users’ preference judgments and interviews. As a consequence of our experiment, we can generally recommend L-shaped leaders as the best compromise between measured task performance and subjective preference ratings, while straight and diagonal leaders received mixed ratings in the two measures. S-shaped leaders are generally not recommended from a practical point of view.
A. Bonerath, J.-H. Haunert, and B. Niedermann. Computing alpha-shapes for temporal range queries on point sets. In Proceedings of the 35rd European Workshop on Computational Geometry (EuroCG'19). 2019. Preprint.
The interactive exploration of data requires data structures that can be repeatedly queried to obtain simple visualizations of parts of the data. In this paper 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.
B. Niedermann, and J.-H. Haunert. Anchored metro maps: combining schematic maps
with geographic maps for multi-modal navigation. In Schematic Mapping Workshop 2019. 2019. Poster abstract.
For conducting navigation tasks in public trans- portation systems, schematic maps (e.g., metro maps) are the first choice, as they reduce the amount of information to a minimum. On the other hand, for navigation tasks in street networks, classical geographic maps are preferable, as they depict the area as accurately as possible. In this work, we create synergies between both types of maps by laying the metro map over the street map. We call those maps anchored metro maps, as we visually attach the metro stations of the metro map to their counterparts on the street map. Currently, we are developing algorithms optimizing the matching between both maps. In future research we plan to use this approach to show that the combination of schematic and geographical maps leads to an improvement for certain navigation tasks.
H.-Y. Wu, B. Niedermann, S. Takahashi, and M. Nöllenburg. A survey on computing schematic network maps: the challenge to interactivity. In Schematic Mapping Workshop 2019. 2019. Preprint.
Schematic maps are in daily use to show the connectivity of subway systems and to facilitate travellers to plan their journeys effectively. This study surveys up-to-date algorithmic approaches in order to give an overview of the state of the art in schematic network mapping. The study investigates the hypothesis that the choice of algorithmic approach is often guided by the requirements of the mapping application. For example, an algorithm that computes globally optimal solutions for schematic maps is capable of producing results for printing, while it is not suitable for computing instant layouts due to its long running time. Our analysis and discussion, therefore, focus on the computational complexity of the problem formulation and the running times of the schematic map algorithms, including algorithmic network layout techniques and station labeling techniques. The correlation between problem complexity and running time is then visually depicted using scatter plot diagrams. Moreover, since metro maps are common metaphors for data visualization, we also investigate online tools and application domains using metro map representations for analytics purposes, and finally summarize the potential future opportunities for schematic maps.
A. Bonerath, B. Niedermann, and J.-H. Haunert. Retrieving alpha-shapes and schematic polygonal approximations for sets of points within queried temporal ranges. In Proc. 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL '19), pages 249-258. 2019. trailer: https://youtu.be/mlnUDhbMSfQ
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.
S. Gedicke, B. Niedermann, and J.-H. Haunert. Multi-page labeling of small-screen maps with a graph-coloring approach. In LBS 2019: 15th International Conference on Location Based Services, November 11-13, 2019, Vienna, AT. 2019.
Annotating small-screen maps with additional content such as labels for points of interest is a highly challenging problem that requires new algorithmic solutions. A common labeling approach is to select a maximum-size subset of all labels such that no two labels constitute a graphical conflict and to display only the selected labels in the map. A disadvantage of this approach is that a user often has to zoom in and out repeatedly to access all points of interest in a certain region. Since this can be very cumbersome, we suggest an alternative approach that allows the scale of the map to be kept fixed. Our approach is to distribute all labels on multiple pages through which the user can navigate, for example, by swiping the pages from right to left. We in particular optimize the assignment of the labels to pages such that no page contains two conflicting labels, more important labels appear on the first pages, and sparsely labeled pages are avoided. Algorithmically, we reduce this problem to a weighted and constrained graph coloring problem based on a graph representing conflicts between labels such that an optimal coloring of the graph corresponds to a multi-page labeling. We propose a simple greedy heuristic that is fast enough to be deployed in web-applications. We evaluate the quality of the obtained labelings by comparing them with optimal solutions, which we obtain by means of integer linear programming formulations. In our evaluation on real-world data we particularly show that the proposed heuristic achieves near-optimal solutions with respect to the chosen objective function and that it substantially improves the legibility of the labels in comparison to the simple strategy of assigning the labels to pages solely based on the labels' weights.
J. Oehrlein, B. Niedermann, and J.-H. Haunert. Analyzing the supply and detecting spatial patterns of urban green spaces via optimization. Journal of Photogrammetry, Remote Sensing and Geoinformation Science (PFG), 87(4):137-158, 2019.
Green spaces in urban areas offer great possibilities of recreation, provided that they are easily accessible. Therefore, an ideal city should offer large green spaces close to where its residents live. Although there are several measures for the assessment of urban green spaces, the existing measures usually focus either on the total size of all green spaces or on their accessibility. Hence, in this paper, we present a new methodology for assessing green-space provision and accessibility in an integrated way. The core of our methodology is an algorithm based on linear programming that computes an optimal assignment between residential areas and green spaces. In a basic setting, it assigns green spaces of a prescribed size exclusively to each resident, such that an objective function that, in particular, considers the average distance between residents and assigned green spaces is optimized. We contribute a detailed presentation on how to engineer an assignment-based method, such that it yields plausible results (e.g., by considering distances in the road network) and becomes efficient enough for the analysis of large metropolitan areas (e.g., we were able to process an instance of Berlin with about 130,000 polygons representing green spaces, 18,000 polygons representing residential areas, and 6 million road segments). Furthermore, we show that the optimal assignments resulting from our method enable a subsequent analysis that reveals both interesting global properties of a city as well as spatial patterns. For example, our method allows us to identify neighborhoods with a shortage of green spaces, which will help spatial planners in their decision-making.
B. Niedermann, and J.-H. Haunert. An algorithmic framework for labeling network maps. Algorithmica, 80(5):1493-1533, 2018.
Drawing network maps automatically comprises two challenging steps, namely laying out the map and placing non-overlapping labels. In this paper we tackle the problem of labeling an already existing network map considering the application of metro maps. We present a flexible and versatile labeling model. Despite its simplicity, we prove that it is NP-complete to label a single line of the network. For a restricted variant of that model, we introduce an efficient algorithm that optimally labels a single line. Based on that algorithm, we present a general and sophisticated workflow for multiple metro lines, which is experimentally evaluated on real-world metro maps.
B. Niedermann, J. Oehrlein, S. Lautenbach, and J.-H. Haunert. A network flow model for the analysis of green spaces in urban areas. In volume 114 of Leibniz International Proceedings in Informatics (LIPIcs). Proc. 10th International Conference on Geographic Information Science (GIScience '18), pages 13:1-13:16. 2018.
Green spaces in urban areas offer great possibilities of recreation, provided that they are easily accessible. Therefore, an ideal city should offer large green spaces close to where its residents live. Although there are several measures for the assessment of urban green spaces, the existing measures usually focus either on the total size of green spaces or on their accessibility. Hence, in this paper, we present a new methodology for assessing green-space provision and accessibility in an integrated way. The core of our methodology is an algorithm based on linear programming that computes an optimal assignment between residential areas and green spaces. In a basic setting, it assigns a green space of a prescribed size exclusively to each resident such that the average distance between residents and assigned green spaces is minimized. We contribute a detailed presentation on how to engineer an assignment-based method such that it yields reasonable results (e.g., by considering distances in the road network) and becomes efficient enough for the analysis of large metropolitan areas (e.g., we were able to process an instance of Berlin with about 130000 polygons representing green spaces, 18000 polygons representing residential areas, and 6 million road segments). Furthermore, we show that the optimal assignments resulting from our method enable a subsequent analysis that reveals both interesting global properties of a city as well as spatial patterns. For example, our method allows us to identify neighborhoods with a shortage of green spaces, which will help spatial planners in their decision making.
B. Niedermann, I. Rutter, and M. Wolf. Efficient algorithms for ortho-radial graph drawing. In Proceedings of the 34rd European Workshop on Computational Geometry (EuroCG'18). 2018. Preprint.
J. Oehrlein, B. Niedermann, and J.-H. Haunert. Inferring the parametric weight of a bicriteria routing model from trajectories. In Proc. 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '17), pages 59:1-59:4. 2017.
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 alpha for a given set of GPS-tracks such that the tracks can be decomposed into a minimum number of optimal paths with respect to alpha. In an experimental evaluation on real-world GPS-tracks of bicyclists we show that our approach yields an appropriate balance factor in a reasonable amount of time.
B. Niedermann, M. Nöllenburg, and I. Rutter. Radial contour labeling with straight leaders. In Proceedings of IEEE Pacific Visualization Symposium (PacificVis'17), pages 295-304. IEEE Computer Society, 2017.
B. Niedermann, M. Nöllenburg, and I. Rutter. Radial contour labeling with straight leaders. In Proceedings of the 33rd European Workshop on Computational Geometry (EuroCG'17). 2017. Preprint
L. Barth, B. Niedermann, I. Rutter, and M. Wolf. Towards a topology-shape-metrics framework for ortho-radial drawings. In Leibniz International Proceedings in Informatics. Proc. 33rd Annual ACM Symposium on Computational Geometry (SoCG '17), pages 14:1-14:16. 2017.
L. Barth, B. Niedermann, I. Rutter, and M. Wolf. Towards a topology-shape-metrics framework for ortho-radial drawings. In Proceedings of the 33rd European Workshop on Computational Geometry (EuroCG'17). 2017. Preprint.
B. Niedermann. Automatic label placement in maps and figures: models, algorithms and experiments. KIT-Bibiliothek. Karlsruher Institut für Technologie (KIT), 2017. Dissertation.
P. Kindermann, B. Niedermann, I. Rutter, M. Schaefer, A. Schulz, and A. Wolff. Multi-sided boundary labeling. Algorithmica, 76(1):225-258, September 2016.
B. Niedermann, and M. Nöllenburg. An algorithmic framework for labeling road maps. In volume 9927 of Lecture Notes in Computer Science. Proceedings of the 9th International Conference on Geographic Information Science (GIScience'16), pages 308-322. Springer, 2016.
L. Barth, B. Niedermann, M. Nöllenburg, and D. Strash. Temporal map labeling: a new unified framework with experiments. In Proc. 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '16), pages 23:1-23:10. ACM, 2016.
A. Gemsa, B. Niedermann, and M. Nöllenburg. Label placement in road maps. In Peter Widmayer, editors, volume 9079 of Lecture Notes in Computer Science. Proceedings of the 9th Conference on Algorithms and Complexity (CIAC'15), pages 221-234. Springer, 2015. Full version available at http://arxiv.org/abs/1501.07188.
L. Barth, A. Gemsa, B. Niedermann, and M. Nöllenburg. On the readability of boundary labeling. In Emilio Di Giacomo, and Anna Lubiw, editors, Lecture Notes in Computer Science. Proceedings of the 23rd International Symposium on Graph Drawing (GD'15). Springer, 2015.
A. Gemsa, B. Niedermann, and M. Nöllenburg. Label placement in road maps. In Proceedings of the 30th European Workshop on Computational Geometry (EuroCG'14). 2014. Preprint.
T. Bläsius, F. Klute, B. Niedermann, and M. Nöllenburg. Pigra - a tool for pixelated graph representations. In Christian A. Duncan, and Antonios Symvonis, editors, volume 8871 of Lecture Notes in Computer Science. Proceedings of the 22nd International Symposium on Graph Drawing (GD'14), pages 513-514. Springer, 2014. Poster abstract.
A. Gemsa, B. Niedermann, and M. Nöllenburg. Trajectory-based dynamic map labeling. In Proceedings of the 29th European Workshop on Computational Geometry (EuroCG'13). 2013.
A. Gemsa, B. Niedermann, and M. Nöllenburg. Trajectory-based dynamic map labeling. In volume 8283 of Lecture Notes in Computer Science. Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC'13), pages 413-423. Springer, 2013. Full version available at http://arxiv.org/abs/1309.3963.
P. Kindermann, B. Niedermann, I. Rutter, M. Schaefer, A. Schulz, and A. Wolff. Two-sided boundary labeling with adjacent sides. In Proceedings of the 29th European Workshop on Computational Geometry (EuroCG'13). 2013.
P. Kindermann, B. Niedermann, I. Rutter, M. Schaefer, A. Schulz, and A. Wolff. Two-sided boundary labeling with adjacent sides. In volume 8037 of Lecture Notes in Computer Science. Algorithms and Data Structures, 13th International Symposium (WADS'13), pages 463-474. Springer, 2013.
T. Biedl, T. Bläsius, B. Niedermann, M. Nöllenburg, R. Prutkin, and I. Rutter. Using ILP/SAT to determine pathwidth, visibility representations, and other grid-based graph drawings. In Stephen K. Wismath, and A. Wolff, editors, volume 8242 of Lecture Notes in Computer Science. Proceedings of the 21st International Symposium on Graph Drawing (GD'13), pages 460-471. Springer, 2013. Full version available at http://arxiv.org/abs/1308.6778.