Traditionally, algorithm design is concerned with the performance in the worst case. The goal is to design algorithms that show the best possible behavior for the worst possible inputs. No attempt is being made to optimize the algorithms for the specific applications at hand. This approach has proved very successful, since it allows us to focus on the underlying structure of the problem at hand, without the distraction of additional assumptions.

On the other hand, there have always been attempts to refine the worst-case model in order to obtain better results. Recently, this research direction has received at lot of attention. Often, computational tasks turn out to be too big and too complex for worst-case algorithms to be feasible. Moreover, real world inputs often contain additional structure that could be exploited for more efficient algorithms.

The goal of the project is to understand this additional structure in the inputs and to begin a systematic study of appropriate models. We would like to find more efficient algorithms that exploit these structures and to develop general techniques for them. The focus will be on problems from computational geometry.