Here we describe some selected research activities of our groups. For complete lists follow these links:

• Angelika Steger's Group
• Emo Welzl's Group
• Peter Widmayer's Group

Average Case Analysis of Algorithms

In average case analysis one considers the typical behaviour of an algorithm. From a practical point of view this is in particular important if the worst case analysis is not satisfactory: it is possible that an algorithm provides empirically good results, even though it has a bad worst case behaviour. The aim of this project is to develop new models and analysis methods for the average case analysis of algorithms.

Combinatorial Models for Geometric Optimization Problems

In the last couple of years new exciting combinatorial models for geometric optimization problems have emerged. For several linear complementarity problems these new combinatorial abstractions provide the only available algorithms with nontrivial running time guarantees. Within this new project, we explore unique-sink orientations, strong LP-type problems, as well as algorithms for problems fitting into the respective models.

Algorithmic Foundations of Ad Hoc and Sensor Networks

Many algorithmic research problems in wireless and/or mobile networks turn out to be variants of classic graph theory and/or computational geometry problems. In this work we try to understand the basic algorithmic foundations and principles of mobile information and communication systems.