Applied Geometric Algorithms

Geometric algorithms, also known as computational geometry, is the field within algorithms research that is concerned with the design and analysis of efficient algorithms and data structures for problems involving geometric objects in 2-, 3-, and higher-dimensional space. The Applied Geometric Algorithms group mainly focuses on geometric algorithms for spatial data and applications of geometric algorithms in the areas of GIScience (including automated cartography and moving object analysis), geo-visualization, visual analytics, and e-humanities. Our approaches frequently combine the rigorous methods from computational geometry - which give performance guarantees with respect to both the quality of solutions and the running time of algorithms - with efficient engineering to achieve results of both theoretical and practical significance.

Geo-Visualization, Automated Cartography, Visual Analytics

(Automated) cartography is focused mostly on the visualization aspects of GIScience and has established itself as its own research area. In recent years the computational aspects of thematic mapping have received considerable interest. Maps are effective tools for communicating information and hence spatial data (and also some non-spatial data) can be visualized well using maps. Thematic maps often depict a single theme or attribute, such as population, income, crime rate, or migration. The map below is a visual summary of some of our recent work in this area.

Flow Map Layout via Spiral Trees K. Verbeek, K. Buchin, and B. Speckmann. IEEE Transactions on Visualization and Computer Graphics, 17(12):2536-2544, 2011.
(Proceedings Visualization / Information Visualization 2011)
Angle-Restricted Steiner Arborescences for Flow Map Layout K. Buchin, B. Speckmann, and K. Verbeek. Algorithmica, 72(2):656-685, 2015.

Clustered Edge Routing Q. Bouts and B. Speckmann. Proc. 8th IEEE Pacific Visualization Symposium (PacificVis), pp. 55-62, 2015. Visual Encoding of Dissimilarity Data via Topology-Preserving Map Deformation Q. Bouts, T. Dwyer, J. Dyke, B. Speckmann, S. Goodwin, N. Riche, S. Carpendale, and A. Liebman. IEEE Transactions on Visualization and Computer Graphics, to appear.

Area-preserving Simplification and Schematization of Polygonal Subdivisions K. Buchin, W. Meulemans, A. van Renssen, and B. Speckmann. ACM Transactions on Spatial Algorithms and Systems, to appear.

Exploring Curved Schematization of Territorial Outlines A. van Goethem, W. Meulemans, B. Speckmann, and J. Wood. IEEE Transactions on Visualization and Computer Graphics, 21(8):889–902, 2015.

Mosaic Drawings and Cartograms R. Cano, K. Buchin, T. Castermans, A. Pieterse, W. Sonke, and B. Speckmann. Computer Graphics Forum, 34(3):361–370, 2015.
(Proc. Eurographics / IEEE Symposium on Visualization (EuroVis) 2015)

StenoMaps: Shorthand for Shapes A. van Goethem, A. Reimer, B. Speckmann, and J. Wood. IEEE Transactions on Visualization and Computer Graphics, 20(12):2053–2062, 2014.
(Proceedings VIS 2014)

Necklace Maps B. Speckmann and K. Verbeek. IEEE Transactions on Visualization and Computer Graphics, 16(6):881–889, 2010.
(Proceedings Visualization / Information Visualization 2010)
Algorithms for Necklace Maps B. Speckmann and K. Verbeek. International Journal of Computational Geometry and Applications, 25(1):15–36, 2015.

Computing the Fréchet Distance between Real-Valued Surfaces K. Buchin, T. Ophelders, and B. Speckmann. In preparation.

Drawing Multiple Crossing-free Geometric Steiner Arborescences I. Kostitsyna, B. Speckmann, and K. Verbeek. In preparation.

Movement Data Analysis

Over the past years the availability of devices that can be used to track moving objects - GPS satellite systems, mobile phones, radio telemetry, surveillance cameras, RFID tags, and more - has increased dramatically, leading to an explosive growth in movement data. Objects being tracked range from animals (for behavioral studies) and cars (for traffic prediction), to hurricanes, sports players (for video analysis of games), and suspected terrorists. Naturally the goal is not only to track objects but also to extract information from the resulting data. Our recent work focuses in particular on the analysis of complex moving objects: non-point objects such as moving polylines (changing coastlines or glacier termini), polygons (hurricanes), and geometric networks (river networks).

Using smoothed Reeb graphs to visualize river data. Work in progress.
Computing the similarity between moving curves K. Buchin, T. Ophelders, and B. Speckmann Proceedings 23rd European Symposium on Algorithms (ESA), pp. 928-940, LNCS 9294, 2015.
Grouping time-varying data for interactive exploration A. van Goethem, M. van Kreveld, M. Löffler, B. Speckmann and F. Staals Proceedings 32nd International Symposium on Computational Geometry (SoCG), 2016.
Visualizing rivers by computing lowest paths. Work in progress.

e-Humanities

The increased digitization of cultural heritage artifacts such as books, manuscripts, or musical scores, creates an ever growing set of highly complex data which humanities researchers aim to analyze and understand. The area of e-humanities, which deals with the development and use of digital technologies in the humanities and social sciences, is hence an intriguing application area for algorithmic visualization with a potentially high impact on society. Our recent work focuses in particular on visual analytics solutions for very large GLAM (meta) data sets.

Visualizing high-dimensional distances in 2D with minimal distortion. Work in progress.
GlamMap: visualising library metadata A. Betti, D.H. Gerrits, B. Speckmann, and H. van den Berg. Proceedings of VALA, 2014. GlamMapping Trove A. Betti, T. Castermans, B. Speckmann, K. Verbeek and H. van den Berg. Proceedings of VALA, 2016.
GlamMap: visualising library metadata A. Betti, D.H. Gerrits, B. Speckmann, and H. van den Berg. Proceedings of VALA, 2014. GlamMapping Trove A. Betti, T. Castermans, B. Speckmann, K. Verbeek and H. van den Berg. Proceedings of VALA, 2016.
Visualizing language status on a map. Work in progress.