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

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 function, …

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 …

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, …


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.

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 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.