Applied Geometric Algorithmslock_outline

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 and Smart Mobility (including Automated Cartography, Geo-Visualization, and Moving Object Analysis), Visual Analytics, Mobile Agents, 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.

Spatially Informed Visualization

Maps are effective tools for communicating information and hence spatial data (and also some non-spatial data) can be visualized well using maps. With spatially informed visualization, we move beyond the typical geographically accurate maps dominating information flows today. We see space as a deformable tool that we can employ to focus attention, give context and accentuate structure in the data while maintaining the key information contained in the spatial dimension. Our algorithmic integration of spatial relevancy with structured information captures the original objectives and vision of traditional cartography. Our focus here lies both on the design of schematic geo-visualizations and on the development of efficient algorithms to create them automatically.

This world map is a visual summary of our work in geo-visualization. Click here to see a large, interactive version.
Travel-Time Maps: Linear Cartograms with Fixed Vertex Locations K. Buchin, A. van Goethem, M. Hoffman, M. van Kreveld, and B. Speckmann. Proc. 8th International Conference on Geographic Information Science (GIScience), pp. 18-33, 2014.
Topologically Safe Curved Schematization A. van Goethem, W. Meulemans, A. Reimer, H. Haverkort, and B. Speckmann. The Cartographic Journal, 50(3):276-285, 2013.
Stenomaps: Shorthand for Shapes A. van Goethem, W. Meulemans, B. Speckmann, and J. Wood. IEEE Transactions on Visualization and Computer Graphics, 20(12):2053-2062, 2014.

Complex Moving Objects

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. 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). We develop algorithms both for basic analysis tasks, such as computing similarities, and to answer applied questions, in collaboration with experts from fields such as physical geography.

Computing the similarity between moving curves K. Buchin, T. Ophelders, and B. Speckmann Proc. 23rd European Symposium on Algorithms (ESA), pp. 928-940, LNCS 9294, 2015.
Multi-Granular Trend Detection for Time-Series Analysis A. van Goethem, F. Staals, M. Löffler, J. Dykes, and B. Speckmann. IEEE Transactions on Visualization and Computer Graphics, 23(1):661–670, 2017. Grouping Time-varying Data for Interactive Exploration A. van Goethem, M. van Kreveld, M. Löffler, B. Speckmann, and F. Staals. Proc. 32nd Annual Symposium on Computational Geometry (SoCG), pp. 61:1–61:16, 2016.
Computing Representative Networks for Braided Rivers M. Kleinhans, M.J. van Kreveld, T.A.E. Ophelders, W.M. Sonke, B. Speckmann, and K.A.B. Verbeek. Proc. 33rd International Symposium on Computational Geometry (SoCG), pp. 48:1-48:16, 2017.
Measuring the distance between two paths on a terrain by computing the volume between them. (Work in progress.)

Stability

Time-varying data like stock prices, traffic status, or weather play an important role in our everyday lives. When creating dynamic visualizations for the purpose of understanding such time-varying data, the stability of the geometric algorithms underlying these visualizations play an important role: small changes in the data should lead to small changes in the visualization. Often there is a tradeoff between the (static) quality of a visualization and its stability. We develop new rigorous tools to measure the stability of geometric algorithms, new methods to analyze the tradeoff between the quality of the output and the stability of algorithms, and new algorithms with provable guarantees on the stability.

Stable Treemaps via Local Moves M. Sondag, B. Speckmann, and K. Verbeek. IEEE Transactions on Visualization and Computer Graphics, 24(1), 2018.
A Framework for Algorithm Stability and its Application to Kinetic Euclidean MSTs W. Meulemans, B. Speckmann, K. Verbeek, and J. Wulms. Proc. 13th Latin American Theoretical Informatics Symposium (LATIN), 805-819, 2018.
Topological stability of k-centers. (Work in progress.)
Stable oriented shape descriptors. (Work in progress.)

Mobile Agents

We explore cross-disciplinary applications of computational geometry to engineering problems motivated by mobile agents. These include path planning and routing of single- and multi-agent systems, assembly and reconfiguration of modular systems, and coordinated distributed computation for programmable matter. Our goal is to develop an algorithmic foundation that supports the design of effective solutions for mobile agent systems.

Forming Tile Shapes with Simple Robots R. Gmyr, K. Hinnenthal, I. Kostitsyna, F. Kuhn, D. Rudolph, C. Scheideler, and T. Strothmann. DNA Computing and Molecular Programming, pp. 122-138, 2018.
Self-Approaching Paths in Simple Polygons P. Bose, I. Kostitsyna, and S. Langerman. Proc. 33rd International Symposium on Computational Geometry (SoCG), 21:1-21:15, 2017.
On the Complexity of Minimum-Link Path Problems I. Kostitsyna, M. Löffler, V. Polishchuk, and F. Staals. Journal of Computational Geometry, 8(2):80-108, 2017.
An Optimal Algorithm to Compute the Inverse Beacon Attraction Region I. Kostitsyna, B. Kouhestani, S. Langerman, and D. Rappaport. Proc. 34th International Symposium on Computational Geometry (SoCG), pp. 55:1-55:14, 2018.
Beacon-Based Algorithms for Geometric Routing M. Biro, J. Iwerks, I. Kostitsyna, and J.S.B. Mitchell. Proc. 13th International Symposium on Algorithms and Data Structures (WADS), pp. 158-169, 2013.

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.

SolarView: Low Distortion Radial Embeddings with a Focus T. Castermans, K. Verbeek, B. Speckmann, M.A.. Westenberg, R. Koopman, S. Wang, H. van den Berg, and A. Betti. IEEE Transactions on Visualization and Computer Graphics, to appear.
GlamMap: visualising library metadata A. Betti, D.H. Gerrits, B. Speckmann, and H. van den Berg. Proc. VALA, 2014. GlamMapping Trove A. Betti, T. Castermans, B. Speckmann, K. Verbeek and H. van den Berg. Proc. VALA, 2016.
GlamMap: visualising library metadata A. Betti, D.H. Gerrits, B. Speckmann, and H. van den Berg. Proc. VALA, 2014. GlamMapping Trove A. Betti, T. Castermans, B. Speckmann, K. Verbeek and H. van den Berg. Proc. VALA, 2016.
GlottoVis: Visualizing Language Endangerment and Documentation T. Castermans, B. Speckmann, K. Verbeek, M.A. Westenberg, and H. Hammarström. Proc. 2nd Workshop on Visualization for the Digital Humanities (VIS4DH), 2017. Simultaneous Visualization of Language Endangerment and Language Description H. Hammarström, T. Castermans, R. Forkel, K. Verbeek, M.A. Westenberg, and B. Speckmann. Language Documentation & Conservation, 12:359—392, 2018.

Map

This world map is a visual summary of some of our work in geo-visualization. Hover over visualizations to view the corresponding publications.

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, 22(9):2200–2213, 2016.

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, 2(1): Article 2, 2016.

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. Proc. 28th Annual Symposium on Discrete Algorithms (SODA), pp. 2443–2455, 2017.

Non-Crossing Geometric Steiner Arborescences I. Kostitsyna, B. Speckmann, and K. Verbeek. Proc. 28th International Symposium on Algorithms and Computation (ISAAC), pp. 54:1–54:13, 2017.