We are happy to announce the Sixth Computational Geometry Challenge,
as part of CG Week in Athens, Greece, June 10-14, 2024.
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 simple polygons, Q_1,…, Q_n, each Q_i with a respective value of c_i,
the task is to find a subset S of {1,…,n} and a feasible
packing within P of the polygons Q_i (without rotation) for i in S.
Objective
Maximize the total value \sum_{i\in S} c_i of the packed polygons.
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) will be announced in the
coming weeks. Appropriate steps will be undertaken (e.g., by restricting
the classes of feasible subsets) to ensure straightforward, automated
verification of solutions, but also ensure original algorithmic contributions.
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 will be
provided for the competition. These will be released at a later time.
(See below.)
Credit
The underlying problem was suggested by Mikkel Abrahamsen, Copenhagen.
References
[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 will be released in late July 2023;
the actual benchmark instances for the Challenge will be 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
**********************************************************
*
* 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
