Understanding, Modeling and Exploiting Structured Inputs for Geometric Problems

• Applicant: Professor Dr. Wolfgang Mulzer
• Subject Area: Theoretical Computer Science
• Term: from 2012 to 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 216333926

The traditional approach for the design and analysis of computer algorithms is based on a worst-case worldview. This means that we aim to obtain algorithms that show the best possible behavior for the worst possible inputs. We do not try to optimize the algorithm for the current context. This worst-case approach has turned out to be very successful. It allows us to focus on the essential properties of the problems at hand, without distracting additional assumptions. At the same time, there have always been attempts to refine this model in order to obtain better results. This direction has recently gained in popularity: on the one hand, the amount of data that needs to be processed has increased dramatically, so that the worst-case approach may not be feasible. On the other hand, real world inputs often have more structure and we have more knowledge about them than what is used by previous approaches.The goal if the current project is to investigate how different kinds of structure in the inputs can be characterized and to understand their properties. In the end, we would like to find more efficient - and simpler - algorithms that exploit this structure. The focus lies on problems from computational geometry.

• DFG Programme: Research Grants