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