Stacking Stars: Minimum-Area Packing with and without Rotation

Abstract

We study the problem of packing a given set of polygons into a minimum-area convex container, that is, placing them without overlap so as to minimize the area of their convex hull. Every previously known polynomial-time algorithm with a nontrivial approximation guarantee for packing polygons with arbitrary edge orientations required the polygons to be convex. In fact, an algorithm was not even known when every input polygon was a quadrilateral. We obtain such algorithms for the entire class of star-shaped polygons with unrestricted combinatorial complexity. The stars may be just translated or also rotated. In either case, we give an $O(\log n)$-approximation algorithm, where $n$ is the number of stars. Likewise, we get $O(\log n)$-approximation algorithms for bin and strip packing, assuming that the diameter of the stars is at most some (small) constant. Previous approximation algorithms for polygon packing focused on convex objects, and the analysis always relied on a density argument, i.e., if the area of the packed objects is at least a fraction $ρ$ of the area of the container, then we have a $(1/ρ)$-approximation. However, star-shaped polygons may need an arbitrarily large area to be packed, even when the total area of the stars approaches $0$ and each star has bounded diameter. This phenomenon prevents the use of density arguments. We instead establish a strong structural property about any packing: Even though the stars can fit together in complicated ways, we can reorganize them into simple stacks, replace these stacks by rectangles, and consider a packing of these rectangles. The rearrangement costs only a factor of $O(\log n)$, which stems from the number of size groups. We complement our algorithms by showing that both the translational and the rotational versions are APX-hard, even for constant complexity stars.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Computational Geometry

• arXiv preprint · 4 November 2026

  Does RRT* Work on Uneven Terrain Meshes?

  Otobong Jerome and Tiago Nascimento
• arXiv preprint · 4 November 2026

  Softmax Attention with Any Temperature in Fixed Dimension: Matching the Best Known Maximum-Inner-Product Bounds

  Zixuan Huang and Guozhang Chen
• arXiv preprint · 4 November 2026

  Constant-Round Massively Parallel Algorithms for Approximate MSTs in Metric Spaces

  Eunjin Oh and Hyeonjun Shin
• arXiv preprint · 4 November 2026

  Resolving Tusnády's Problem

  Nicola Wengiel
• arXiv preprint · 3 November 2026

  Binary Huffman Coding with Unequal Letter Costs Is NP-Complete

  L. Sunil Chandran and Rishikesh Gajjala

All new papers in Computational Geometry