## CG Challenge: Solving Hard Optimization Problems

The Second Geometric Optimization Challenge takes place as part of CG Week in
Zurich, Switzerland, June 22-26, 2020.

As in the last year, the objective will be to compute good solutions to
instances of a difficult geometric optimization problem. The contributors with
the most outstanding solutions will be recognized at the workshop at CG Week
and invited to present their results. The specific problem chosen for the
2020 Challenge is the following:

### Minimum Convex Partition

Given a set S of n points in the plane. The objective is to compute a plane
graph with vertex set S (with each point in S having positive degree) that
partitions the convex hull of S into the smallest possible number of convex
faces.

The complexity of this problem is still unknown, but
approximation algorithms have been proposed; e.g., see Christian Knauer and
Andreas Spillner: Approximation
Algorithms for the Minimum Convex Partition Problem, SWAT 2006,
pp. 232-241.

### Dates

- Contest opens 18:00 CEDT (noon, EDT), September 30, 2019.
- Contest closes 24:00 (midnight, AoE), February 14, 2020.
- Invitations for proceedings contributions: February 21, 2020.
- Final versions of proceedings contributions due: March 31, 2020.

### Submissions

For all further details about the competition (such as benchmark instances,
data formats, and rules for submission and evaluation), please refer to the challenge
webpage.

### Organization

- Erik Demaine (MIT)
- Sándor Fekete (TU Braunschweig)
- Phillip Keldenich (TU Braunschweig)
- Dominik Krupke (TU Braunschweig)
- Joseph S. B. Mitchell (Stony Brook University)