The Fifth Computational Geometry Challenge will be part of CG Week
in Athens, Greece, June 10-14, 2024.
There is still plenty of time to participate - or introduce it to your students!
(Contest closes January 27 - 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 2023 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) 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 rule out simple use of commercial solvers.
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.
Credit:
This 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 was released in late September 2022;
the actual benchmark instances for the Challenge were released
in October. The contest will close in late January 2023.
• First test instances: September 30, 2022
• Contest instances: October 28, 2022
• Contest Closes: January 27, 2023
**********************************************************
*
* 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
