We are happy to announce the Sixth Computational Geometry Challenge, as part of CG Week in Athens, Greece, June 11-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.
Given a convex region, $P$, in the plane, and a collection of simple polygons, $Q_i,\dots,Q_n$, each $Q_i$ with a respective value of $c_i$, the task is to find a subset $S$ of $1,\dots,n$ and a feasible packing within $P$ of the polygons $Q_i$ (without rotation) for $i\in S$.
Maximize the total value $\sum_{i\in S}c_i$ of the packed polygons.
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.
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!
A large number and variety of input polygonal regions P are provided for the competition. Make sure to download the actual challenge instances and not the example instances, as only those are evaluated.
Details of the competition (such as benchmark instances, data formats, and rules for submission and evaluation) can be found on the website:
https://cgshop.ibr.cs.tu-bs.de/competition/cg-shop-2024/#problem-descriptionThe underlying problem was suggested by Mikkel Abrahamsen, Copenhagen.
[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.