Algorithms, Geometry & Applicationslock_outline

The ALGA cluster (Algorithms, Geometry, and Applications) studies the design and analysis of algorithms and data structures, one of the core areas within computer science. Research in ALGA ranges from curiosity-driven to motivated by concrete applications, and from purely theoretical to experimental. In all cases, the goal is to understand the underlying principles of the developed solutions and to formally prove their properties. Our approaches frequently combine the rigorous methods from algorithmic theory – 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.

Within the broad field of algorithms, ALGA specializes in various areas:

Computational Geometry
Moving Object Analysis
Parameterized Complexity
Geovisualization
Massive Data
Mobile Agents
Networks
Digital Humanities

Computational Geometry

Computational geometry is the area within algorithms research dealing with the design and analysis of algorithms and data structures for spatial data. It combines clever algorithmic techniques with beautiful geometric concepts to obtain efficient solutions to algorithmic problems involving spatial data. We study fundamental algorithmic as well as combinatorial problems in this area, with the aim of developing an algorithmic foundation to tackle geometric problems arising in other domains.

Moving Object Analysis

Over the past years the availability of devices that can be used to track moving objects – GPS satellite systems, mobile phones, 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. We develop algorithms both for basic analysis tasks, such as clustering, and to answer questions from domain scientists. Our work encompasses both point trajectory data (cars, animals, …) and moving non-point objects (hurricanes, river networks, …). A particular focus are models and algorithms for data uncertainty and stability (small changes in the data should lead to small changes in the result).

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.
Topological stability of k-centers. (Work in progress.)

Parameterized Complexity

Parameterized complexity offers a rigorous toolset to develop exact algorithms for NP-hard problems. The goal is to develop algorithms which are provably efficient on inputs whose complexity, as measured by natural parameters, is limited. This gives much needed insights into many computationally hard problems that would be unreachable by the standard toolset. An important subfield is kernelization, which is the formal study of efficient preprocessing. It develops reduction rules which reduce the size of an input without changing the answer. Applying such reduction rules as a preprocessing step can speed up algorithms by several orders of magnitude.

Fine-grained complexity of k-OPT in bounded-degree graphs for solving TSP Edouard Bonnet, Yoichi Iwata, Bart M. P. Jansen, and Lukasz Kowalik Proc. 27th European Symposium on Algorithms (ESA), pp. 23:1-23:14, 2019.
A Turing kernelization dichotomy for structural parameterizations of F-minor-free deletion Huib Donkers and Bart M. P. Jansen Proc. 45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pp. 106-119, 2019.
Turing kernelization for finding long paths and cycles in restricted graph classes Bart M. P. Jansen Journal of Computer and System Sciences (85), pp. 18-37, 2017.
Computing the chromatic number using graph decompositions via matrix rank Bart M. P. Jansen and Jesper Nederlof Theoretical Computer Science (795), pp. 520-539, 2019.

Geovisualization

Maps are effective tools for visualizing and communicating spatial data. Algorithms play an important role in automated cartography and geovisualization, for example, in placing elements and connections, and creating scale-appropriate representations. Our work encompasses the design and computation both of thematic maps and of spatially informed visualizations, that move beyond the typical geographically accurate maps. A particular focus are schematic geovisualizations where we apply a deliberate, controlled deformation of space to give context and accentuate structure in the data, while maintaining key spatial aspects.

This world map is a visual summary of our work in geo-visualization. Please check out the 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.

Massive Data

Big data is everywhere. One increasingly important type of big data is in the form of networks: gene regulatory networks, disease networks, and social networks. Most of these networks are not static: the data constantly evolves according to some unknown but measurable dynamics. As the network behavior evolves over time, the resulting data becomes too large and comes in too fast to even store in the computer’s memory, requiring (sketching and sampling-based) algorithms (1) to manipulate the data immediately as it streams by using relatively little memory, or (2) to parallelize the data on a big number of machines having moderate memory by using few communication rounds.

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.

Networks

Networks for communication, transportation, finance and energy form the backbone of modern society. Hence, it is important to design and use networks in the most efficient manner. This leads to many challenging algorithmic questions concerning the design and maintenance of good network structures as well as the performance of processes running on the network. For example, how can we design networks that are sparse while still providing a relatively short path between every pair of nodes? We study algorithmic questions for abstract networks as well as for networks that are embedded in geometric spaces.

Digital Humanities

The increased digitization of cultural heritage artifacts, such as books or manuscripts, as well as the prevalence of social media, create an ever-growing set of highly complex data which humanities researchers aim to analyze and understand. Recent advances in the accuracy of language analysis technologies, relying on generic language models trained on vast amounts of data, enable automated analysis of humanities data, but also pose a challenge: language models are essentially black boxes and it is unclear what exactly they learn and how. Our recent work focuses on visual analytics solutions for data exploration as well as topological analysis of high dimensional semantic spaces.

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.