The Sixth Computational Geometry Challenge will be part of CG Week
in Athens, Greece, June 10-14, 2024.
https://cgshop.ibr.cs.tu-bs.de/competition/cg-shop-2024/
There is still plenty of time to participate - or introduce it to your students!
(Contest closes January 22 - see times below.)
As in previous years, the objective will be to compute good solutions
to instances of a difficult geometric optimization problem.
The specific problem chosen for the 2024 Challenge is
Maximum Polygon Packing, as follows.
Description:
Given a convex region, P, in the plane, and a collection
of polygons, Q_1,…, Q_n, each with a respective value of c_i.
The task is to find a subset S of {1,…,n} and a feasible
packing of all Q_i (without rotation!) with i in S into P.
Objective:
Maximize the total value \sum_{i\in S} c_i of the packed objects.
Motivation:
Optimal packing problems have an extensive history in Computational Geometry.
They are also relevant in many practical contexts.
Even the one-dimensional version of the problem (the Knapsack Problem)
is NP-hard; furthermore, some geometric variants have been shown to be
∃R-complete [1], which most likely implies that they are not in the class NP.
Details of the competition (such as benchmark instances, data formats,
specific constraints on feasible packings, such as integer coordinates,
as well as rules for submission and evaluation) can be found on the website.
The contributors with the most outstanding solutions will be recognized
at CG Week 2024 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!
Instances:
A large number and variety of input polygonal regions P are
provided for the competition. You can download them on
the competition's website.
Credit:
This problem was suggested by Mikkel Abrahamsen, Copenhagen.
Reference:
[1] M. Abrahamsen, T. Miltzow and N. Seiferth,
"Framework for ER-Completeness of Two-Dimensional Packing Problems,"
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 2020,
pp. 1014-1021, doi: 10.1109/FOCS46700.2020.00098.
Challenge Team:
Sándor Fekete, Phillip Keldenich, Dominik Krupke, Stefan Schirra
Advisory Board:
Bill Cook, Andreas Fabri, Dan Halperin, Michael Kerber,
Philipp Kindermann, Joe Mitchell, Kevin Verbeek
Timeline:
A first batch of test instances has been released in late July 2023; the actual benchmark instances for the Challenge have been released in late September. The contest will close in early 2024.
* First test instances: July 31, 2023
* Contest instances: September 29, 2023
* Contest Closes: January 22, 2024 (AOE)
For inquiries or issues, please feel free to send a brief email to cgshop-admin@ibr.cs.tu-bs.de.
**********************************************************
*
* 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
