A Formal Approach to the Automated Labeling of Groups of Features
A. Reimer, A.I. Goethem, van, M. Rylov, M.J. Kreveld, van and B. Speckmann.
Cartography and Geographic Information Science, 42(4) pp. 333—344, 2015.
－ Abstract
A variety of recurring geographic entities form collections of point, line, or area features. Examples are groups of islands (Archipelago), relief features in deserts, periglacial lakes or geomorphological forms, such as drumlins and sinkholes. All these groups of features might be best identified with a single label. Surprisingly, the (automated) labeling of groups of features has received little attention so far. We propose a framework to determine formal measures that describe the geometric aspects of the cartographic design space for labeling feature groups. Our framework gives rise to a large variety of geometrically optimal labels. We list the optimal label positions and shapes for which labels can already be computed using existing algorithms. However, in many of the cases computing optimal label placements is still an open algorithmic question which can readily be investigated in future work. Once the necessary algorithms are developed, our framework provides an objective basis to investigate the geometric measures used by cartographers to label groups of features. We preliminarily explore the applicability of our framework using one of the geometric optimality choices.
Keywords: automated cartography, labeling, groups of features
－ BibTeX
@inbook{a-formal-approach-to-the-automated-labeling-of-groups-of-features-2015,
title = "A Formal Approach to the Automated Labeling of Groups of Features",
author = "",
year = "2015",
booktitle = "",
}
[ PDF ]
Algorithms for Necklace Maps
B. Speckmann and K.A.B. Verbeek.
International Journal of Computational Geometry and Applications, 25(1) pp. 15—36, 2015.
－ Abstract
Necklace maps visualize quantitative data associated with regions by placing scaled symbols, usually disks, without overlap on a closed curve (the necklace) surrounding the map regions. Each region is projected onto an interval on the necklace that contains its symbol. In this paper we address the algorithmic question how to maximize symbol sizes while keeping symbols disjoint and inside their intervals. For that we reduce the problem to a one-dimensional problem which we solve efficiently. Solutions to the one-dimensional problem provide a very good approximation for the original necklace map problem.
We consider two variants: Fixed-Order, where an order for the symbols on the necklace is given, and Any-Order where any symbol order is possible. The Fixed-Order problem can be solved in O(n log n) time. We show that the Any-Order problem is NP-hard for certain types of intervals and give an exact algorithm for the decision version. This algorithm is fixed-parameter tractable in the thickness K of the input. Our algorithm runs in O(n log n + n2K4K) time which can be improved to O(n log n + nK2K) time using a heuristic. We implemented our algorithm and evaluated it experimentally.
Keywords: Necklace maps; scheduling; automated cartography
－ BibTeX
@inbook{algorithms-for-necklace-maps-2015,
title = "Algorithms for Necklace Maps",
author = "",
year = "2015",
booktitle = "",
}
[ PDF ]
Angle-Restricted Steiner Arborescences for Flow Map Layout
K. Buchin, B. Speckmann and K.A.B. Verbeek.
Algorithmica, 72(2) pp. 656—685, 2015.
－ Abstract
We introduce a new variant of the geometric Steiner arborescence problem, motivated by the layout of flow maps. Flow maps show the movement of objects between places. They reduce visual clutter by bundling curves smoothly and avoiding self-intersections. To capture these properties, our angle-restricted Steiner arborescences, or flux trees, connect several targets to a source with a tree of minimal length whose arcs obey a certain restriction on the angle they form with the source.
We study the properties of optimal flux trees and show that they are crossing-free and consist of logarithmic spirals and straight lines. Flux trees have the shallow-light property. We show that computing optimal flux trees is NP-hard. Hence we consider a variant of flux trees which uses only logarithmic spirals. Spiral trees approximate flux trees within a factor depending on the angle restriction. Computing optimal spiral trees remains NP-hard, but we present an efficient 2-approximation, which can be extended to avoid "positive monotone" obstacles.
Keywords: Steiner arborescences; Flow maps; Computational geometry; Automated cartography
－ BibTeX
@inbook{angle-restricted-steiner-arborescences-for-flow-map-layout-2015,
title = "Angle-Restricted Steiner Arborescences for Flow Map Layout",
author = "",
year = "2015",
booktitle = "",
}
[ PDF ]
Exploring Curved Schematization of Territorial Outlines
A.I. Goethem, van, W. Meulemans, B. Speckmann and J.D. Wood.
IEEE Transactions on Visualization and Computer Graphics, 21(8) pp. 889—902, 2015.
－ Abstract
Hand-drawn schematized maps traditionally make extensive use of curves. However, there are few automated approaches for curved schematization; most previous work focuses on straight lines. We present a new algorithm for areapreserving curved schematization of territorial outlines. Our algorithm converts a simple polygon into a schematic crossing-free representation using circular arcs.We use two basic operations to iteratively replace consecutive arcs until the desired complexity is reached. Our results are not restricted to arcs ending at input vertices. The method can be steered towards different degrees of "curviness": we can encourage or discourage the use of arcs with a large central angle via a single parameter. Our method creates visually pleasing results even for very low output complexities. To evaluate the effectiveness of our design choices, we present a geometric evaluation of the resulting schematizations. Besides the geometric qualities of our algorithm, we also investigate the potential of curved schematization as a concept. We conducted an online user study investigating the effectiveness of curved schematizations compared to straight-line schematizations. While the visual complexity of curved shapes was judged higher than that of straight-line shapes, users generally preferred curved schematizations. We observed that curves significantly improved the ability of users to match schematized shapes of moderate complexity to their unschematized equivalents.
Keywords: Schematization; algorithm; circular arcs; user study
－ BibTeX
@inbook{exploring-curved-schematization-of-territorial-outlines-2015,
title = "Exploring Curved Schematization of Territorial Outlines",
author = "",
year = "2015",
booktitle = "",
}
[ PDF ]
Improved Grid Map Layout by Point Set Matching
D. Eppstein, M.J. Kreveld, van, B. Speckmann and F. Staals.
International Journal of Computational Geometry and Applications, 25(2) pp. 101—122, 2015.
－ Abstract
Associating the regions of a geographic subdivision with the cells of a grid is a basic operation that is used in various types of maps, like spatially ordered treemaps and Origin-Destination maps (OD maps). In these cases the regular shapes of the grid cells allow easy representation of extra information about the regions. The main challenge is to find an association that allows a user to find a region in the grid quickly. We call the representation of a set of regions as a grid a grid map.
We introduce a new approach to solve the association problem for grid maps by formulating it as a point set matching problem: Given two sets A (the centroids of the regions) and B (the grid centres) of n points in the plane, compute an optimal one-to-one matching between A and B. We identify three optimisation criteria that are important for grid map layout: maximise the number of adjacencies in the grid that are also adjacencies of the regions, minimise the sum of the distances between matched points, and maximise the number of pairs of points in A for which the matching preserves the directional relation (SW, NW, etc.). We consider matchings that minimise the L1-distance (Manhattan-distance), the ranked L1-distance, and the L22-distance, since one can expect that minimising distances implicitly helps to fulfill the other criteria.
We present algorithms to compute such matchings and perform an experimental comparison that also includes a previous method to compute a grid map. The experiments show that our more global, matching-based algorithm outperforms previous, more local approaches with respect to all three optimisation criteria.
Keywords: Grid map; point-set matching; visualization
－ BibTeX
@inbook{improved-grid-map-layout-by-point-set-matching-2015,
title = "Improved Grid Map Layout by Point Set Matching",
author = "",
year = "2015",
booktitle = "",
}
[ PDF ]
Mosaic Drawings and Cartograms
R.G. Cano, K. Buchin, T.H.A. Castermans, A. Pieterse, W.M. Sonke and B. Speckmann.
Computer Graphics Forum, 34(3) pp. 361—370, 2015.
－ Abstract
Cartograms visualize quantitative data about a set of regions such as countries or states. There are several different types of cartograms and – for some – algorithms to automatically construct them exist. We focus on mosaic cartograms: cartograms that use multiples of simple tiles – usually squares or hexagons – to represent regions. Mosaic cartograms communicate well data that consist of, or can be cast into, small integer units (for example, electorial college votes). In addition, they allow users to accurately compare regions and can often maintain a (schematized) version of the input regions’ shapes. We propose the first fully automated method to construct mosaic cartograms. To do so, we first introduce mosaic drawings of triangulated planar graphs. We then show how to modify mosaic drawings into mosaic cartograms with low cartographic error while maintaining correct adjacencies between regions. We validate our approach experimentally and compare to other cartogram methods.
－ BibTeX
@inbook{mosaic-drawings-and-cartograms-2015,
title = "Mosaic Drawings and Cartograms",
author = "",
year = "2015",
booktitle = "",
}
[ PDF ]
Trajectory Grouping Structure
K.A. Buchin, M.E. Buchin, M.J. van Kreveld, B. Speckmann and F. Staals.
Journal of Computational Geometry, 6(1) pp. 75—98, 2015.
－ Abstract
The collective motion of a set of moving entities like people, birds, or other animals, is characterized by groups arising, merging, splitting, and ending. Given the trajectories of these entities, we define and model a structure that captures all of such changes using the Reeb graph, a concept from topology. The trajectory grouping structure has three natural parameters that allow more global views of the data in group size, group duration, and entity inter-distance. We prove complexity bounds on the maximum number of maximal groups that can be present, and give algorithms to compute the grouping structure efficiently. We also study how the trajectory grouping structure can be made robust, that is, how brief interruptions of groups can be disregarded in the global structure, adding a notion of persistence to the structure. Furthermore, we showcase the results of experiments using data generated by the NetLogo flocking model and from the Starkey project. The Starkey data describe the movement of elk, deer, and cattle. Although there is no ground truth for the grouping structure in this data, the experiments show that the trajectory grouping structure is plausible and has the desired effects when changing the essential parameters. Our research provides the first complete study of trajectory group evolvement, including combinatorial,<br/>algorithmic, and experimental results.<br/>
－ BibTeX
@inbook{trajectory-grouping-structure-2015,
title = "Trajectory Grouping Structure",
author = "",
year = "2015",
booktitle = "",
}
[ PDF ]