Computational Geometry:
Solving Hard Optimization Problems

Geometric Optimization Challenges

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

Past Competitions

Ended on: May 31, 2019, midnight UTC
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.
Ended on: Feb. 14, 2020, 11:59 p.m. UTC
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: Feb. 16, 2021, 11:59 a.m. UTC
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.