As previously announced, the Second Geometric Optimization Challenge will
be part of CG Week in Zurich, Switzerland, June 22-26, 2020, and is about to begin:
Contest opens 12:00 (noon, EDT), September 30, 2019.
Contest closes 24:00 (midnight, AoE), February 14, 2020.
We are happy to announce that space in the SoCG proceedings (to be published
with LIPIcs) will be provided to the top performing teams, with invitations for the
submission of articles issued immediately after the conclusion of the contest. (In addition,
there may be an invitation for selected submissions to be considered for publication in the
ACM Journal on Experimental Algorithms, either as part of a special issue or as invited
submissions.)
As in 2019's Challenge, 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.
Further details are available via the challenge webpage,
https://cgshop.ibr.cs.tu-bs.de/competition/cg-shop-2020/
including a link for downloading problem instances, and to the submission
site for uploading solutions.
IMPORTANT NOVELTY:
In addition to the „Open Class" of the Challenge, in which solutions are only judged based on the
number of convex faces obtained (using any type of available computing equipment), we are
considering the introduction of a „Limited Class", which will be based on timed
execution on specific equipment at our site, with evaluation based on test runs for additional
benchmark instances. In addition, we would offer a „Junior Class" for teams consisting
exclusively of junior researchers.
As the setup for such a „Limited Class" comes with serious additional effort on our side,
we want to be sure that this is worth it. If you are interested in participating in these variants,
please write to us by October 14:
(1) Drop us a line/email voicing your interest.
(2) Add specific preferences or recommendations, if you have any.
Based on the feedback, we may announce further steps and details.
We are looking forward to your submissions!
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
