CS Paper Radar

Stacking Stars: Minimum-Area Packing with and without Rotation

Mikkel Abrahamsen, Jacobus Conradi, Arindam Khan, Jack Stade, Sampson Wong, Shuyi Yan, Hanwen Zhang

cs.CG cs.DS ·submitted 2026-11-04 20:11 UTC · v1

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.

Comment
52 pages, 35 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Geometric Bin Packing Beyond Convexity: Approximation Schemes without Augmentation

cs.CG cs.DS ·2026-11-03 ·Lucas de Oliveira Silva, Elisa Dell'Arriva, Flávio Keidi Miyazawa
similarity 0.77
Abstract

We study the geometric bin packing problem for simple polygonal regions, i.e., non-degenerate, connected, rational regions, in the minimum number of unit-square bins, allowing only translations. We even consider packing general non-convex objects, possibly with holes, where we can then pack smaller objects. Previous schemes cover squares (MOR'06), circles and other $L_p$-balls (Algorithmica'16), sufficiently skewed rectangles (Algorithmica'23), and convex fat objects with a constant number of distinct shapes under resource augmentation (arXiv'24, WAOA'23). The result for circles and other $L_p$-balls needs bin augmentation to obtain rational packing realizations. For restricted classes of $L$-shaped polygons, Gerlach et al. (SoCG'26) give constant worst-case guarantees, while for general non-convex objects, bounding-box reductions give just approximation factors that depend on fatness. Against this background, we present a general framework that provides asymptotic polynomial-time approximation schemes (APTAS) for bin packing of any fixed class of simple polygonal regions satisfying just two assumptions. First, covering any object by the grid cells intersecting its interior in any sufficiently fine square grid, relative to the object's bounding box, increases its area by at most a small fraction. Second, the class can be partitioned into a constant number of sequences such that each object in a sequence can be translated to fit inside every preceding object. In particular, certain classes of star-shaped polygons and more general polygonal regions, including some with simple holes, satisfy both assumptions. In addition, our framework does not require a bound on the objects' boundary complexity. We emphasize that our results require no bin augmentation whatsoever and yield explicit, exact rational packings of polynomial encoding length for all input objects.

0.29

Improved Approximation for Weighted $k$-Set Packing via a Simple Two-Phase Approach

cs.DS ·2026-11-16 ·Mehrshad Taziki, Rico Zenklusen
similarity 0.66
Abstract

Weighted $k$-set packing asks for a maximum-weight collection of pairwise disjoint sets, each of cardinality at most $k$. For every fixed $k\in\mathbb Z_{\geq1}$, we give a polynomial-time algorithm with approximation factor $\left(1- 1/{\sqrt3} \right)k+O(\log k) \approx 0.4226k + O(\log k)$, improving the previous best factor of $0.4621k + O(\sqrt{k})$ through a simple two-phase approach. In a first phase, our algorithm constructs a packing by processing random weight buckets of varying widths with an unweighted packing algorithm. We show that a small expected weight of this packing relative to the optimum forces a large expected total surplus in the optimum. Surplus quantifies the potential for improving a packing through star swaps. In the second phase, we solve and round a configuration LP to turn sufficiently large surplus into an increase in expected weight. Our procedure can easily be derandomized.

0.30

Triangle Covers of Polygons: Approximation Algorithms and Complexity

cs.CG ·2026-10-16 ·Linda Kleist, Lena Scherzer
similarity 0.64
Abstract · 37 pages, 32 figures, GeoGebra file

We study the geometric set cover problems of covering and partitioning a polygon into a minimum number of triangles. While the decision version of the covering problem is known to be APX-hard and $\exists\mathbb R$-complete (even for polygons without holes and vertices in general position), the computational complexity of partitioning a simple polygon into a minimum number of triangles is open. Our main result refutes a 40 year old conjecture by Asano, Asano, and Pinter stating that the triangle vertices of a minimum partition lie on intersection points of special lines, which are iteratively generated by the polygon vertices and the intersection points. In particular, we show that there exist polygons where all minimum triangle partitions need Steiner points with irrational coordinates. This indicates that the problem might be more complex than previously expected. Complementarily, we provide a simple constant factor approximation to compute a minimum triangle partition of a given polygon (possibly with holes). In the context of coverings, we devise the first constant factor approximation for computing a minimum triangle cover of a simple polygon. For general polygons, an $O(\log n)$-approximation follows by close inspection of previous work.

0.27

The Containment Polytope of a Triangle and a Convex Polygon

cs.CG ·2026-11-05 ·Yoonsung Choi, Sunghee Choi
similarity 0.62
Abstract

The containment polytope $\mathcal{C}$ for a triangle $P$ and a convex $n$-gon $Q$ is a four-dimensional polytope representing the similarity transforms (translation, rotation, scaling) that place $P$ inside $Q$. While it is known that the complexity of $\mathcal{C}$ and its silhouette $Λ$, which represents all the largest placements of $P$ inside $Q$ for all orientations, can be quadratic in $n$, we show that the silhouette can be partitioned into a linear number of planar convex chains and steps in $O(n \log n)$ time. Based on the linear number of convex chains and steps, we can compute the complexity of silhouette $Λ$ in $O(n \log n)$ time and query the largest placement of $P$ inside $Q$ for a given orientation in $O(\log n)$ time. We explain geometrically how the triangle $P$ rotates while continuously scaling and translating to be maximal inside $Q$, leading to a parameterized algorithm for containment problems.

0.25

Curves of constant width and Lebesgue's covering problem

cs.CG math.MG ·2026-08-31 ·Ujjwal Mishra
theory similarity 0.61
Abstract

A universal cover is a convex set in the plane that contains a congruent copy of every planar set of diameter one. Lebesgue asked in 1914 for one of least area, and the value is not known. We prove that every convex universal cover has area at least 0.8344, improving on 0.832, published in 2005, and 0.833, in a 2026 preprint, both of which come from a disc together with an equilateral triangle and a regular pentagon. Our test sets are instead curves of constant width: the disc, the Reuleaux triangle and the Reuleaux pentagon. Each contains the regular polygon it is built on, so the family is strictly larger at the same number of bodies and the same number of placement parameters, and we show that the classical configuration admits an arrangement whose hull has area below 0.8336, so no bound drawn from those three sets by this argument reaches ours. Curves of constant width were proposed for this role, and explored numerically, by Gibbs in 2014; what is added here is a proof. It consists of an analytic reduction followed by one finite computation. The reduction bounds the hull area from below over an entire box of placements at once, by eroding each Reuleaux polygon to a fixed set contained in every placement that box allows. The computation is an exhaustive subdivision of the resulting five-dimensional space, recorded as a certificate of 486,799,600 nodes and checked by a verifier independent of the search, with a rigorous bound on its floating point error some thousands of times smaller than the margin the verification attains.

0.16

Packing Tails of Reciprocal Rectangles into Squares of Equal Area

cs.DM math.CO ·2026-09-23 ·Yu Jiang
theory similarity 0.60
Abstract · Blog is coming soon

The Meir--Moser rectangle-packing problem asks whether all rectangles with side lengths \(1/n\) and \(1/(n+1)\), for \(n\ge1\), can be packed into the unit square with pairwise disjoint interiors. We establish a tail version of this problem. Let \(R_n\) denote the rectangle with these side lengths. We prove that there exists an integer \(m_0\) such that, for every \(m\ge m_0\), the family \(\{R_n:n\ge m\}\) admits a packing, by translations and right-angle rotations, into a square of side length \(m^{-1/2}\), with pairwise disjoint interiors. The area of the square equals the sum of the areas of all the rectangles. The geometric construction recursively decomposes rectangular gaps, while local randomized quotas and random permutations assign subsequent integer indices. We separately control the total area of waiting gaps and the assignment load at each index. The proof is organized in six steps: a finite-prefix reduction, geometric row decompositions, an area bootstrap, a sharp source-load estimate, control of the actual adaptive construction, and a compactness limit. For every finite time horizon, the probability of failure has a bound that is independent of the horizon and can be made arbitrarily small. The adaptive step uses a permanent load ledger, actual fresh height queries, and a one-sided comparison with a frozen source experiment. Compactness then yields an infinite packing. The final packing statements have been checked in Lean 4. A sufficient threshold is \(m_0=10^{1000}\). This result applies only to sufficiently late tails and does not resolve the original Meir--Moser rectangle-packing problem for the full sequence starting at \(n=1\), which remains open.

0.14

Computing the minimal perimeter polygon for digital objects in the triangular tiling

cs.CG ·2026-09-12 ·Petra Wiederhold
published similarity 0.60
Abstract · Preprint from November 11, 2024

This work presents an algorithm, together with its correctness proof, to determine the minimum perimeter polygon (MPP) for digital objects given as regular complexes in the triangular plane tiling. Such objects are edge-adjacency-connected sets of triangle tiles that have no end tiles, and the point set union of all their tiles forms a simple polygon. Nevertheless, the boundary paths of the objects are not assumed to be simple. Then the MPP is a weakly simple polygon that coincides with the relative convex hull (i.e., geodesic hull) of a set $A$ with respect to a simple polygon $B$, where $A\subset B$, but $A$ is not necessarily a polygon, in fact it is generally not connected. Our MPP algorithm relies on constructing and iteratively constraining cones of visibility through forthcoming boundary tiles, it uses the structure of the canonical boundary path, the MPP frontier is the shortest polygonal curve following this path. We also propose a boundary tracing algorithm to obtain such paths from the objects.

0.58

Maximum Edge Open Packing on AT-Free, Chordal, and Convex Bipartite Graphs

cs.DM math.CO ·2026-10-01 ·Gautam K. Das, Kamal Santra
similarity 0.59
Abstract

An edge open packing is a set of edges whose endpoints induce a disjoint union of stars. We study the problem of finding a maximum edge open packing in AT-free, chordal, and convex bipartite graphs. For AT-free graphs, we use the oriented star-conflict graph $A_G$, introduced by Das and Santra, for which $ρ_e^o(G)=α(A_G)$, and prove that $A_G$ is AT-free whenever $G$ is AT-free. Consequently, a known maximum independent set algorithm for AT-free graphs yields an $O(n^2+m^4)$-time algorithm for Maximum Edge Open Packing, where $n$ and $m$ denote the numbers of vertices and edges of $G$, respectively. For chordal graphs, we develop an $O(n^4)$-time dynamic programming algorithm over a nice tree decomposition derived from a clique tree, exploiting the structural fact that the endpoint set of an edge open packing intersects every clique in at most two vertices. Finally, for convex bipartite graphs, we obtain an $O(n^4)$-time dynamic programming algorithm based on two boundary indices that separate consecutive star components. This result extends the previously known algorithm for biconvex bipartite graphs and, in particular, provides an improved explicit running-time bound for that class.

0.07