CGAL users discussion list

[Monique Teillaud <>]

> De: "Sándor Fekete" 
> <>
> À: "compgeom-announce" 
> <>,
>  
> ,
>  
> 
> Cc: "Sándor Fekete" 
> <>,
>  "edemaine" 
> <>,
>  "Joseph Mitchell"
> <>,
>  "Dominik Krupke" 
> <>,
>  "Phillip Keldenich"
> <>
> Envoyé: Jeudi 5 Septembre 2019 20:32:28
> Objet: [compgeom-announce] First Announcement: CG Challenge 2020

> 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