Maximum Polygon Packing: The CG:SHOP Challenge 2024

Abstract

We give an overview of the 2024 Computational Geometry Challenge targeting the problem \textsc{Maximum Polygon Packing}: Given a convex region $P$ in the plane, and a collection of simple polygons $Q_1,\dots ,Q_n$, each $Q_i$ with a respective value $c_i$, find a subset $S\subseteq \{1,\dots ,n\}$ and a feasible packing within $P$ of the polygons $Q_i$ (without rotation) for $i\in S$, maximizing ${\sum }_{i\in S}{c}_i$. Geometric packing problems, such as this, present significant computational challenges and are of substantial practical importance.

16 pages, 10 figures