[hpc-announce] First Announcement: CG Challenge 2020

[Sándor Fekete]

Dear colleagues,

We are happy to announce the Second Geometric Optimization Challenge, 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 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.

Details of the competition (such as benchmark instances, data formats, and 
rules for submission and evaluation) will be announced in coming weeks.

Contest opens   18:00 CEDT (noon, EDT), September 30, 2019.
Contest closes   24:00 (midnight, AoE), February 14, 2020.

The contributors with the most outstanding solutions will be recognized at the workshop at 
CG Week and invited  to present their results. In addition, it is planned that the top contributing 
teams will be invited to submit their results to be included in a high-level publication; details 
will be announced shortly, by the time the contest opens.

We are looking forward to your contributions and welcome questions and comments!

Erik Demaine, Sándor Fekete, Phillip Keldenich, Dominik Krupke, Joe Mitchell