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
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
