CG Week logo CG Week
 

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

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