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

11/08/2024
1:49 p.m.

Technical Issues from Nov, 8th, 7:30 CET to 10:00 CET

We recently experienced a temporary issue with our database management system (DBMS). The issue has been resolved, and we do not believe any data has been lost. However, as a precaution, we recommend the following actions:

  • If …
09/30/2024
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 …

06/28/2024
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.

...


Active Competitions

Ends at: Jan. 22, 2025, 11:59 p.m. (AoE)
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

Ended on: Jan. 22, 2024, 11:59 p.m. (AoE)
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.
Ended on: Jan. 27, 2023, 11:59 p.m. (AoE)
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.
Ended on: Jan. 19, 2022, 11:59 p.m. (AoE)
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.
Ended on: Feb. 15, 2021, 11:59 p.m. (AoE)
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.
Ended on: Feb. 14, 2020, 11:59 a.m. (AoE)
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.
Ended on: May 30, 2019, noon (AoE)
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.