[hpc-announce] [compgeom-announce] Fourth Computational Geometry Challenge - First Announcement

[Sándor Fekete]

Dear friends and colleagues,

A first batch of test instances is now online:

https://cgshop.ibr.cs.tu-bs.de/competition/cg-shop-2022/#instance-format

These are not the contest instances yet, but meant for training purposes,
running first tests, etc. If you encounter any problems, questions or
suggestions, please get in touch - that kind of interaction is an intended
part of this phase, so we can fine-tune the difficulty of the actual challenge.

Best wishes,
Sándor Fekete, Phillip Keldenich, Dominik Krupke, Stefan Schirra



> Am 21.07.2021 um 14:02 schrieb Sándor Fekete <s.fekete at tu-bs.de>:
> 
> Dear colleagues,
> 
> We are happy to announce the Fourth Geometric Optimization Challenge, as 
> part of CG Week in Berlin, Germany, June 7-10, 2022.
> 
> See https://cgshop.ibr.cs.tu-bs.de/competition/cg-shop-2022/#problem-description
> 
> 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 2022 Challenge is the following:
> 
> Minimum Partition into Plane Subgraphs
> -----------------------------------------------------
> 
> Given a geometric graph G=(V,E), with vertices represented by points in the plane,
> and edges by straight-line connections between vertices.
> 
> The task is to partition E into as few subsets E_1,…, E_k as possible, such that
> each subgraph G_i=(V,E_i) is plane: In the given geometric representation,
> line segments representing edges my touch at end points if and only if the 
> corresponding edges are incident in G_i; no edges my cross, i.e., share
> points that are not segment end points.
> 
> The problem is related to a variety of classic problems, ranging from coloring and 
> graph partitioning to extremal graph theory. For example, edge coloring in planar 
> graphs H (for which it is a long-standing conjecture [2] that it is NP-hard for graphs 
> of maximum degree Δ=4 or 5  to decide whether they have an edge coloring with 
> Δ colors) is a special case: From a straight-line drawing of H, slightly extend all 
> line segments, so that they cross at the vertices of H, and nowhere else.
> 
> The related problem of partitioning a geometric graph into a minimum number of 
> plane spanning trees has also received considerable attention; see Aichholzer et al. [1] 
> for an overview.
> 
> Details of the competition (such as benchmark instances, data formats, and rules for 
> submission and evaluation) will be announced in coming weeks; see the timeline below.
> 
> The contributors with the most outstanding solutions will be recognized at CG Week 
> and invited to present their results, both at the event and in the proceedings.
> 
> We are looking forward to your contributions and welcome questions and comments!
> 
> Challenge Team:
> ----------------------
> Sándor Fekete, Phillip Keldenich, Dominik Krupke, Stefan Schirra
> 
> Advisory Board:
> ---------------------
> Bill Cook, Andreas Fabri, Michael Kerber, Philipp Kindermann, Joe Mitchell, Kevin Verbeek
> 
> Timeline:
> ------------
> - By August 19, 2020: 	Release of first test instances
> 
> - September 19, 2021: 	Contest instances, contest opens
> 
> - January 19, 2022:		Contest closes
> 
> - March 15, 2021: 		Final versions of proceedings contributions due
> 
> Credit:
> ---------
> This problem was suggested by Johannes Obenaus, FU Berlin.
> 
> References:
> ----------------
> 
> [1]
> Marek Chrobak, Takao Nishizeki.
> Improved edge-coloring algorithms for planar graphs.
> Journal of Algorithms, Volume 11, Issue 1, March 1990, Pages 102-116.
> 
> [2]
> Oswin Aichholzer, Thomas Hackl, Matias Korman, Marc van Kreveld, Maarten Löffler, 
> Alexander Pilz, Bettina Speckmann, Emo Welzl.
> Packing plane spanning trees and paths in complete geometric graphs
> Information Processing Letters, Volume 124, August 2017, Pages 35-41;
> full version available at https://arxiv.org/abs/1707.05440
> 
> -- 
> You are currently subscribed to compgeom-announce.
> To unsubscribe or access the archives, go to
> https://sympa.inria.fr/sympa/info/compgeom-announce
> 
> 
> 
>