Computational Geometry:
Solving Hard Optimization Problems
Geometric Optimization Challenges
The CG:SHOP Challenge (Computational Geometry: Solving Hard Optimization Problems) is an annual competition dedicated to tackling specific, difficult geometric optimization problems. Originally established as a workshop at Computational Geometry Week (CG Week) in 2019, the Challenge provides a unique platform where the success of proposed solutions is measured based on computational performance on a set of carefully selected benchmark instances. This focus on empirical evaluation marks a shift from traditional computational geometry research, which often emphasizes theoretical approaches.
Each year, the CG:SHOP Challenge invites participants from diverse fields—including computational geometry and combinatorial optimization—to devise and implement innovative solution methods for a new optimization problem. Past challenges have addressed a range of problems, such as computing minimum and maximum area polygons from vertex sets, coordinated motion planning, and minimum convex partitioning. With each challenge, we aim to foster collaboration, rigorous comparison of methods, and an opportunity for hands-on problem-solving experience for students and researchers alike.
Join us in the upcoming CG:SHOP Challenge to push the boundaries of geometric optimization, share ideas, and contribute to the vibrant community of computational problem-solvers at CG Week!
News
7:57 a.m.
The challenge instance for CG:SHOP 2025 are now online!
We are also providing a PyUtils package to verify your solutions, as well as a naive solver you can use to get started. We will need some days to set up the evaluation system, due to the more complex scoring …
6:07 p.m.
First Announcement: CG Challenge 2025
We are happy to announce the Seventh Computational Geometry Challenge, as part of CG Week in Kanazawa, Japan, June 23-27, 2025.
As in previous years, the objective will be to compute good solutions to instances of a difficult geometric optimization problem. The specific problem chosen for the 2025 Challenge is Minimum Non-Obtuse Triangulations, as follows.
...
9:44 a.m.
CG:SHOP Challenge 2025: Call for Problems
Since 2019, the CG:SHOP Challenge has been part of CG Week. The objective is to compute good solutions for instances of a challenging geometric optimization problem. The contributors with the most outstanding solutions are recognized at CG Week and invited to present their …
Active Competitions
CG:SHOP 2025
Organized by: Sándor Fekete , Phillip Keldenich , Dominik Krupke , Stefan Schirra
The Seventh Geometric Optimization Challenge is part of CG Week 2025. The task is to compute Minimum Non-Obtuse Triangulations.
Review the problem description for more details.Past Competitions
CG:SHOP 2024
Organized by: Sándor Fekete , Phillip Keldenich , Dominik Krupke , Stefan Schirra
The sixth Geometric Optimization Challenge was part of CG Week 2024. The task was Maximum Polygon Packing.
Review the problem description for more details.CG:SHOP 2023
Organized by: Sándor Fekete , Phillip Keldenich , Dominik Krupke , Stefan Schirra
The fifth Geometric Optimization Challenge was part of CG Week 2023. The task was Minimum Coverage by Convex Polygons.
Review the problem description for more details.CG:SHOP 2022
Organized by: Sándor Fekete , Phillip Keldenich , Dominik Krupke , Stefan Schirra
The fourth Geometric Optimization Challenge was part of CG Week in Berlin, Germany, June 6-10, 2022. The task was to solve the Minimum Partition into Plane Subgraphs Problem.
Review the problem description for more details.CG:SHOP 2021
Organized by: Sándor Fekete , Phillip Keldenich , Dominik Krupke , Joseph S. B. Mitchell
The third Geometric Optimization Challenge was part of CG Week 2021. The problem was to compute a set of collision-free parallel motions for unit-square robots on a pixel grid.
Review the problem description for more details.CG:SHOP 2020
Organized by: Erik Demaine , Sándor Fekete , Phillip Keldenich , Dominik Krupke , Joseph S. B. Mitchell
The second Geometric Optimization Challenge was part of CG Week in Zurich, Switzerland, June 22-26, 2020. The task was to solve the Minimum Convex Partition Problem, which asks for a set of edges connecting a given set of points which partitions the convex hull of the points into the minimum number of convex regions.
Review the problem description for more details.CG:SHOP 2019
Organized by: Erik Demaine , Sándor Fekete , Joseph S. B. Mitchell
The first Geometric Optimization Challenge was part of a workshop at CG Week 2019. The problem was to compute polygons with minimal or maximal area for a given point set.
Review the problem description for more details.