CGAL users discussion list

[Monique Teillaud <>]

> De: "Sándor Fekete" 
> <>
> À: "compgeom-announce" 
> <>,
>  
> 

> Dear colleagues,
> 
> 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