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):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
@article{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 = {A. Reimer and A.I. Goethem, van and M. Rylov and M.J. Kreveld, van and B. Speckmann},
year = {2015},
bookTitle = {Cartography and Geographic Information Science},
}
[ PDF ]
Algorithms for Necklace Maps
B. Speckmann and K.A.B. Verbeek.
International Journal of Computational Geometry and Applications,
25(1):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
@article{algorithms-for-necklace-maps:2015,
title = {Algorithms for Necklace Maps},
author = {B. Speckmann and K.A.B. Verbeek},
year = {2015},
bookTitle = {International Journal of Computational Geometry and Applications},
}
[ PDF ]
Angle-Restricted Steiner Arborescences for Flow Map Layout
K. Buchin, B. Speckmann, and K.A.B. Verbeek.
Algorithmica,
72(2):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
@article{angle-restricted-steiner-arborescences-for-flow-map-layout:2015,
title = {Angle-Restricted Steiner Arborescences for Flow Map Layout},
author = {K. Buchin and B. Speckmann and K.A.B. Verbeek},
year = {2015},
bookTitle = {Algorithmica},
}
[ 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):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
@article{exploring-curved-schematization-of-territorial-outlines:2015,
title = {Exploring Curved Schematization of Territorial Outlines},
author = {A.I. Goethem, van and W. Meulemans and B. Speckmann and J.D. Wood},
year = {2015},
bookTitle = {IEEE Transactions on Visualization and Computer Graphics},
}
[ PDF ]
[ 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):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
@article{improved-grid-map-layout-by-point-set-matching:2015,
title = {Improved Grid Map Layout by Point Set Matching},
author = {D. Eppstein and M.J. Kreveld, van and B. Speckmann and F. Staals},
year = {2015},
bookTitle = {International Journal of Computational Geometry and Applications},
}
[ 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):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
@article{mosaic-drawings-and-cartograms:2015,
title = {Mosaic Drawings and Cartograms},
author = {R.G. Cano and K. Buchin and T.H.A. Castermans and A. Pieterse and W.M. Sonke and B. Speckmann},
year = {2015},
bookTitle = {Computer Graphics Forum},
}
[ 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):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
@article{trajectory-grouping-structure:2015,
title = {Trajectory Grouping Structure},
author = {K.A. Buchin and M.E. Buchin and M.J. van Kreveld and B. Speckmann and F. Staals},
year = {2015},
bookTitle = {Journal of Computational Geometry},
}
[ PDF ]
Geometric K Shortest Paths
S. Eriksson-Bique, J. Hershberger, V. Polishchuk, B. Speckmann, S. Suri, T. Talvitie, K.A.B. Verbeek, and H. Yildiz.
Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15, San Diego CA, USA, January 4-6, 2015),
pp. 1616—1625,
2015.
- Abstract
We consider the problem of computing k shortest paths in a two-dimensional environment with polygonal obstacles, where the jth path, for 1 = j = k, is the shortest path in the free space that is also homotopically distinct from each of the first j – 1 paths. In fact, we consider a more general problem: given a source point s, construct a partition of the free space, called the kth shortest path map (k-SPM), in which the homotopy of the kth shortest path in a region has the same structure. Our main combinatorial result establishes a tight bound of T(k2h + kn) on the worst-case complexity of this map. We also describe an O((k3h + k2n) log (kn)) time algorithm for constructing the map. In fact, the algorithm constructs the jth map for every j = k. Finally, we present a simple visibility-based algorithm for computing the k shortest paths between two fixed points. This algorithm runs in O(m log n + k) time and uses O(m + k) space, where m is the size of the visibility graph. This latter algorithm can be extended to compute k shortest simple (non-self-intersecting) paths, taking O(k2 m(m + kn) log (kn)) time.
We invite the reader to play with our applet demonstrating k-SPMs [10].
- BibTeX
@article{geometric-k-shortest-paths:2015,
title = {Geometric K Shortest Paths},
author = {S. Eriksson-Bique and J. Hershberger and V. Polishchuk and B. Speckmann and S. Suri and T. Talvitie and K.A.B. Verbeek and H. Yildiz},
year = {2015},
bookTitle = {Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15, San Diego CA, USA, January 4-6, 2015)},
}
[ PDF ]