Computational Geometry:
Solving Hard Optimization Problems

Geometric Optimization Challenges

We host optimization challenges for computational geometry problems. The challenges are part of CG Week.

News

05/27/2024
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 results, …

01/18/2024
10:51 a.m.

With only a few days left, participants are reminded of the approaching submission deadline. If you face any issues during submission, please email us with your team's name and a hash of your solution files. Once you have the files ready, follow up with a link for us to access them.

09/29/2023
8:05 p.m.

I am pleased to announce that the instances for our competitions are now available for download. Furthermore, we have successfully implemented the solution upload functionality. However, please note that the verification process for submitted solutions will commence in a few weeks' time.


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 is part of CG Week 2024.

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 is part of CG Week 2023.

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 is part of CG Week in Berlin, Germany, June 6-10, 2022. The task is 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

Third CG:SHOP competition as part of CG Week 2021. The problem is 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 is part of CG Week in Zurich, Switzerland, June 22-26, 2020. The task is 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

First CG:SHOP competition as 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.