Computational Geometry: Solving Hard Optimization Problems

The goal of CG:SHOP (Computational Geometry: Solving Hard Optimization Problems) is to combine theoretical methods from Computational Geometry and Mathematical Optimization with practical techniques from Algorithm Engineering to achieve provably good solutions for instances of practically relevant size for difficult problems of practical relevance. In the first phase (2020-25), we considered a variety of specific geometric optimization problems (such as covering and dispersion, structure problems, and touring problems), as well as more generic aspects (such as sparsification, errors and objectives, and toolbox), leading to about 20 publications so far, with an additional 25+ papers by other authors.

In the second phase (which starts in January 2026), we study a number of specific problem areas based on structure, tour, covering and packing problems, and pursue more universal perspectives developing general methodologies for solution and instance space analysis, as well as activities in the global research community.