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 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.
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).
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.
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.
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.
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.
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.
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.