[This page is currently under construction and will be gradually supplemented.]
CG:SHOP is a research project dedicated to the development of new methods for challenging geometric optimization problems. Since 2020, the project has been led by the Technical University Braunschweig in collaboration with several international research partners, and the first funding phase has already been successfully completed. The project is currently continuing in its second funding phase supported by the German Research Foundation (DFG). The goal of the project is to combine theoretical approaches from computational geometry with practical methods from algorithm engineering in order to develop efficient algorithms for realistic problem sizes.
In addition to the original research objectives, the first funding phase also initiated the annual CG:SHOP Challenge, an international competition in which selected geometric optimization problems are provided and research teams develop and evaluate new algorithmic solution approaches. Further information about the CG:SHOP Challenge can be found on the official website.
One research focus in the area of geometric structure problems addressed the polygonization of point sets. The task is to construct a simple polygon from a given set of points such that all points appear as vertices and certain optimization criteria are satisfied, for example maximizing (MAX-AREA) or minimizing (MIN-AREA) the enclosed area. S. P. Fekete et al. conducted a systematic study of different exact solution approaches for the MIN-AREA and MAX-AREA problem. In particular, two different integer optimization models, an edge-based formulation and a triangulation-based formulation, were developed and compared.
Using the improved formulations, S. P. Fekete et al. were able to solve a larger number of instances to optimality compared to previous approaches. Their results also demonstrate that polygonization problems such as MIN-AREA and MAX-AREA are practically more challenging than classical optimization problems such as the Euclidean Traveling Salesman Problem.
Another research focus in the area of touring problems concerned the Lawn Mowing Problem. In this problem, the goal is to compute a shortest closed tour for a region bounded by a polygon such that every point in this region lies within a given maximum distance from the tour. Intuitively, this can be understood as moving a disk with this maximum distance as its radius along the tour such that every point in the region is covered by the disk at least once. The problem generalizes several well-known geometric optimization problems and occurs in numerous practical applications, for example in robotics or manufacturing processes.
In their work on the Lawn Mowing Problem, which received the Best Paper Award at ALENEX 2023, S. P. Fekete et al. obtained significant results. They first showed that optimal tours always consist of a polygonal chain with finitely many vertices. This means that infinitely many points within the region to be covered can be represented by a finite set of vertices, which significantly restricts the solution space and forms the basis for algorithmic approaches.
In addition, they developed a primal-dual algorithm that iteratively extends an initial finite set of “witness points”. For these points, an approximate solution is computed by solving a Close-Enough TSP, thereby providing both an upper bound, meaning a feasible tour, and a lower bound for the optimal tour. Each iteration reduces the remaining optimality gap and thus enables provably near-optimal solutions for large instances.
Building on the success of the first funding phase, CG:SHOP2 aims to develop new methods for computing provably optimal or near-optimal solutions for a broad class of geometric optimization problems. The project continues to investigate concrete problem classes from the first phase, including structure problems, touring problems, and packing problems, while simultaneously developing general algorithmic tools and analysis methods.
A particularly successful initiative that emerged from the first funding phase is the CG:SHOP Challenge, which has been held annually since 2019. This international competition focuses on a different challenging geometric optimization problem each year. Research teams as well as individual participants develop new algorithmic approaches and compare their methods on shared benchmark instances. The CG:SHOP Challenge combines theoretical questions from computational geometry with practical algorithmic techniques and realistic problem sizes.
The CG:SHOP Challenge has quickly developed into an important meeting point for the international research community. Through this open competition, new datasets, implementations, and algorithmic ideas are created, many of which lead to scientific publications. At the same time, the challenge provides a platform for early-career researchers to present their methods and compare them with established research teams.
Prof. Dr. Sándor P. Fekete
Algorithmics Group
Technical University Braunschweig
Mühlenpfordtstraße 23
38106 Braunschweig
Phone: +49 (0)531 391 311 1
Fax: +49 (0)531 391 310 9
Email: s.fekete@tu-bs.de
Website: Prof. Dr. Fekete at TU Braunschweig