betaFeedback

WorksComputer Science

Polylogarithmic Approximation for Packing Convex Polyhedra

Abstract

We study translational packing of convex polyhedra in three dimensions. Given nn convex polyhedra in R3\mathbb{R}^3, we seek a placement with pairwise disjoint interiors that minimizes the volume of an axis-parallel bounding box. Constant-factor approximation algorithms are known when rotations are allowed, but no approximation guarantee was previously known for arbitrary convex polyhedra with fixed orientations. A central difficulty is that, unlike in the plane, the total volume and the coordinate extents of the objects do not provide a useful lower bound on the optimum: even objects with small total volume and small diameter may require a container of large volume. We overcome this difficulty using a better geometric lower bound based on a surprising connection to Wang and Zahl's celebrated recent proof of the three-dimensional Kakeya conjecture. Using this, we obtain a polynomial-time no(1)n^{o(1)}-approximation algorithm. A recent strengthening of Wang and Zahl's theorem claimed by OpenAI gives a polylogarithmic approximation ratio for the same algorithm. Our ideas extend to bin and strip packing: for any fixed δ>0δ>0, we obtain the same approximation guarantees for translational packing of convex polyhedra whose coordinate widths are at most a 1−δ1-δ fraction of the corresponding container widths.

Introduction

Packing problems are among the most fundamental problems in discrete and computational geometry. We study the packing of convex polyhedra in three dimensions using translations only. Given nn convex polyhedra K1,…,KnK_1,\ldots,K_n in R3\mathbb{R}^3, the goal is to translate them into an axis-parallel box of minimum volume so that their interiors are pairwise disjoint. Boundary contact is allowed. We denote OPTvol\mathrm{OPT}_{\mathrm{vol}} for this minimum volume.

Beyond their theoretical appeal, three-dimensional packing problems are of considerable practical importance, with classical applications in container loading, pallet loading, and cutting stock, and more recent applications in additive manufacturing (3D printing). In powder-based technologies such as selective laser sintering, many parts are produced in a single machine run, and because spreading each layer of powder takes much longer than sintering it, the parts should be nested as densely as possible in the build volume [18]. The resulting layout is a major factor in the material cost and production time of a job [31], and the nesting problem has received considerable attention in the manufacturing literature; see the surveys [36, 8].

The translational case is particularly relevant in additive manufacturing, where the build orientation of each part is usually chosen before nesting because it determines surface quality, the required support structures, and the build time and cost [22, 9]. The parts are then placed using translations, possibly combined with rotations about the vertical axis [36, 9]. Similar restrictions arise in the plane, where the grain or pattern of a material such as fabric may prevent pieces from being rotated [2]; such constraints have motivated the study of translational packing of convex polygons [6, 30, 2].

The packing literature is vast; see the surveys [13, 3, 14, 4] [43] with references to hundreds of articles on three-dimensional packing. Most theoretical work in three dimensions concerns packing axis-parallel cuboids by translations into bins, a strip, or a minimum-volume box, a line of research dating back to the 1960s [21, 34]. Since the work of Li and Cheng [33], approximation algorithms have been developed for three-dimensional bin packing and strip packing [15, 35, 20, 27, 11, 10, 26, 40] and for related knapsack and hypercube packing problems [17, 24].

The emphasis on cuboids reflects what is tractable rather than the range of shapes appearing in practice. Parts to be printed are rarely cuboids, yet studies of production planning for additive manufacturing often approximate them by rectangles or cuboids to simplify nesting [36]. Practical approaches that handle general polyhedra directly rely on heuristics and mathematical programming models without performance guarantees [19, 18, 31] [41]; see [32] for a review of such models.

Results. Since the problem is NP-hard even for axis-parallel cuboids [7], we aim for approximation algorithms and prove the following main result.

Theorem 1. There is a polynomial-time no(1)n^{o(1)}-approximation algorithm for translational packing of nn convex polyhedra in R3\mathbb{R}^3 into a minimum-volume axis-parallel box.

More precisely, for every ε>0\varepsilon> 0, the approximation ratio is at most CεnεC_\varepsilon n^\varepsilon for some constant CεC_\varepsilon, while the algorithm and its running time are independent of ε\varepsilon. The constant CεC_\varepsilon depends on unspecified constants in Wang and Zahl’s Kakeya estimate [42], so we do not make the o(1)o(1) term explicit.

This paper was essentially complete when OpenAI announced a proof of Sogge’s local smoothing conjecture [38], accompanied by a Lean formalization [37]. The formalization proves a stronger bound than Wang and Zahl’s on the volume of unions of direction-separated tubes, while the preprint claims a theorem that would yield an even stronger bound and has not been formally verified. Both make our approximation ratio polylogarithmic, as stated in the following theorem, which is proven in Appendix § 9.

Theorem 2. Using OpenAI’s formally verified tube estimate [37], the algorithm of Theorem 1 achieves approximation ratio O(log⁡69n)O(\log^{69} n). If the Kakeya maximal estimate claimed by OpenAI [38 Corollary 9.1] holds, the ratio improves to O(log⁡7n)O(\log^7 n).

We consider the minimum-volume box to be the most basic container objective, but the applications also lead to other objectives. In additive manufacturing, the build volume of the machine is fixed, and one wants to minimize the number of runs needed to produce a given set of parts or, within a single run, the height of the layout, which determines the number of layers and hence the build time [18, 36]. These are the three-dimensional versions of two classical problems: in bin packing, the objects have to be packed into the minimum number of unit cubes, and in strip packing, they have to be packed into a container [0,1]2×[0,h][0,1]^2 \times[0,h] of minimum height hh. For cuboids, all three objectives have been studied with closely related techniques [7, 29]. Our techniques carry over to bin packing and strip packing of convex polyhedra under translations, provided that the extend of the objects is bounded away from that of the container.

Theorem 3. Suppose that translational packing of convex polyhedra in R3\mathbb{R}^3 into a minimum-volume axis-parallel box admits a polynomial-time α\alpha-approximation. Then, for every 0<δ<10 < \delta< 1, translational bin packing and strip packing of convex polyhedra with coordinate widths at most 1−δ1-\delta admit polynomial-time O(α/δ3)O(\alpha/\delta^3)- and O(α/δ2)O(\alpha/\delta^2)-approximation algorithms, respectively.

We prove Theorem 3 in § 5. By Theorem 1, we can take α=no(1)\alpha= n^{o(1)}, and by Theorem 2, even α=O(log⁡69n)\alpha= O(\log^{69} n).

Previous Techniques. Known constant-factor approximation algorithms for packing convex objects rely on what we call the volume lower bound, which combines total area or volume with the space needed to accommodate individual objects [6, 7]. For translational packing in the plane, for example, this bound is

OPT⁡area≥max⁡{∑iarea⁡(Ki),wxwy},(1)\operatorname{OPT}_{\mathrm{area}} \ge\max\left\{\sum_i \operatorname{area}(K_i), w_x w_y\right\}, \tag*{(1)}

where OPT⁡area\operatorname{OPT}_{\mathrm{area}} is the minimum area of an axis-parallel rectangle containing a translational packing, and wx,wyw_x,w_y are the maximum widths of the input polygons in the respective coordinate directions.

In the plane, even under translations, Alt, de Berg, and Knauer [6, 16] gave constant-factor approximations for packing convex polygons, and Kurpisz and Suter [30] improved the factor for minimum-area rectangles to 9.459.45. Their analysis shows that the volume lower bound (1) suffices for a constant-factor approximation.

Analogous versions of the volume lower bound are particularly useful under rigid motions, where rotations are allowed: they yield constant-factor approximations for packing cuboids and general convex objects [6, 7]. The same approach extends to any fixed dimension dd, with constants depending on dd.

Whether a constant-factor approximation exists for translational packing of arbitrary convex polyhedra in three dimensions has repeatedly been posed as an open question [39, 5, 1]. Theorem 1 gives the first approximation guarantee for this problem. Table 1 summarises the known results on minimum-area and minimum-volume packing.

Rigid motionsTranslations
2DConvex polygons: O(1)O(1) [6]Convex polygons: 9.45 [30]
3DConvex polyhedra: O(1)O(1) [7]Axis-parallel cuboids: O(1)O(1) [7], 3+ε3+\varepsilon and APTAS [29]
3DUnit disks (planar) in R3\mathbb{R}^{3}: O(1)O(1) [5]
3DCongruent planar shapes: O(ρ3)O(\rho^{3}) [5]
3DConvex polyhedra: no(1)n^{o(1)}, O(log⁡69n)O(\log^{69} n), O(log⁡7n)O(\log^{7} n) (this work)

Table 1. Approximation guarantees for minimum-area (2D) and minimum-volume (3D) axis-parallel containers. Rigid motions allow rotations. For congruent planar shapes, ρ\rho is the ratio of enclosing to inscribed disk radii.

For fixed orientations in three dimensions, the volume/max-extent bound (1) can be far too small. Consider nn unit-radius planar disks in R3\mathbb{R}^{3}, with arbitrary normal vectors: their total three-dimensional volume is zero and each coordinate width is at most 22, so the bound is at most 88. Yet there are choices of normal vectors for which every translational packing requires volume Ω(n)\Omega(\sqrt{n}) [5]. Enclosing these disks in sufficiently thin convex polyhedra gives the same obstruction with full-dimensional objects. One of the missing ingredients to obtain packing algorithms in three dimensions is therefore a stronger lower bound on the cost of the optimal solution that captures the space consumption forced by such different orientations. The second ingredient is an algorithm that comes close to this new lower bound.

For unit disks, Alt, Cabello, Cheong, Park, and Seiferth [5] obtain such a lower bound through a Hamiltonian-path formulation. They prove that in any packing, the disks can be rearranged into stacks, with the disk centers on lines in the directions of the three coordinate axis. Placing the disks like that defines a metric, which is the distance between centers. It follows that arranging the disks according to a constant factor approximation of the shortest Hamiltonian path yields a constant-factor approximation algorithm. The argument relies on equal radii, and the authors state the case of disks having different radii as an open problem. They extend the algorithm for unit disks to congruent copies of a single planar shape, however this loses a factor of O(ρ3)O(\rho^{3}), where ρ\rho is the ratio of the radii of an enclosing and inscribed disk of the shape. Thus this gives no uniform guarantee for arbitrary polyhedra.

The Kakeya volume estimate and its relation to packing.

Our geometric input is the following consequence of Wang and Zahl’s theorem [42]. For v∈S2v \in S^{2}, x∈R3x \in\mathbb{R}^{3}, and δ>0\delta> 0, the tube Tδ(v,x)T_{\delta}(v,x) is the open δ\delta-neighbourhood of the unit segment {x+tv:∣t∣≤1/2}\{x+tv : |t| \le1/2\}. For δ≤1\delta\le1, it has volume πδ2+43πδ3≤73πδ2\pi\delta^{2}+\frac{4}{3}\pi\delta^{3}\le\frac{7}{3}\pi\delta^{2}. For vectors v,w∈R3∖{0}v,w \in\mathbb{R}^{3}\setminus\{0\}, we define the unoriented angle between them to be the minimum of the angle between viv_i and vjv_j and the angle between viv_i and −vj-v_j.

Theorem 4. *For every ε>0\varepsilon>0, there exists a constant Cε≥1C_{\varepsilon}\ge1 such that the following holds for all 0<δ≤10<\delta\le1. Let v1,…,vm∈S2v_1,\ldots,v_m\in S^{2} be such that for distinct i,ji,j, the unoriented angle between viv_i and vjv_j

is at least δ\delta, and let x1,…,xm∈R3x_1,\ldots,x_m \in\mathbb{R}^3. Then

vol⁡(⋃i=1mTδ(vi,xi))≥δεCε∑i=1mvol⁡(Tδ(vi,xi)).\operatorname{vol}\left(\bigcup_{i=1}^{m} T_{\delta}(v_i,x_i)\right) \ge\frac{\delta^{\varepsilon}}{C_{\varepsilon}}\sum_{i=1}^{m}\operatorname{vol}(T_{\delta}(v_i,x_i)).

In Appendix A we prove that Theorem 4 follows from [42, Theorem 1.2].

Kakeya lower bounds. We briefly discuss why the Kakeya volume estimate is useful for providing lower bounds for packings. Our main concern is flat pieces where a volume bound is insufficient. For a packing of such flat pieces, it turns out to be a very useful technique to identify a subset of the pieces such that after thickening them to some thickness τ\tau, there is a linear transformation that maps the pieces to approximate Kakeya tubes. Then the Kakeya volume estimate tells us that there cannot be too much overlap between the thickened pieces, and the volume occupied by the thickened pieces can be lower bounded in terms of the sums of their volumes. Within constant factors, the cost of an optimal solution is at least that of the volume occupied by thickened pieces, so this gives a lower bound of its cost in terms of the number of such pieces. We discuss this in a bit more detail below.

Discussion of our techniques

We enclose the polyhedra in parallelepipeds and round two edge parameters to obtain O(log⁡2n)O(\log^2 n) types, with only a constant-factor enlargement. Within each type, the shadows (projections) onto the yzyz-plane all have the same area AA, and their shadows fall into a discrete set of possible parallelograms. In the following, we explain how we handle a single type.

Upper bound. We stack objects with the same shadow by placing their centres on a line parallel to the xx-axis so that their shadows coincide. The space needed depends on how closely consecutive objects fit together, and this separation cost defines a metric on each shadow group. Choosing an order with minimum total separation is therefore a metric Hamiltonian-path problem. We use the classic MST-based 2-approximation to order each group and then combine the stacks. Writing MSTk\mathrm{MST}_k for the tree weight of shadow group kk, the resulting packing has volume O(OPTvol+A∑kMSTk)O(\mathrm{OPT}_{\mathrm{vol}}+A\sum_k\mathrm{MST}_k), where OPTvol\mathrm{OPT}_{\mathrm{vol}} is the optimal cost for packing this type of pieces.

Lower bound. We need a lower bound on the optimum in terms of the same spanning-tree weights. For intuition, imagine that all tree-edge lengths belong to {1n,2n,4n,…,1}\left\{\frac{1}{n},\frac{2}{n},\frac{4}{n},\ldots,1\right\}, giving only O(log⁡n)O(\log n) possible values for the scale. Some value, say τ1\tau_1, accounts for Ω((∑kMSTk)/log⁡n)\Omega((\sum_k \mathrm{MST}_k)/\log n) of the total weight, so there are Ω((∑kMSTk)/(τ1log⁡n))\Omega((\sum_k \mathrm{MST}_k)/(\tau_1\log n)) edges of that length. These edges of the MSTs allow us to select m=Ω((∑kMSTk)/(τ1log⁡n))m=\Omega((\sum_k \mathrm{MST}_k)/(\tau_1\log n)) representative objects such that any two from the same shadow group have distance at least τ1\tau_1. Indeed, by the MST property, after removing the edges of length at least τ\tau, we end up with connected components such that the distance between any two pieces in different connected components is at least τ\tau, so we can select a representative from each such component. Start with any feasible packing (in particular, an optimal one) and thicken each representative in the xx-direction to thickness Θ(τ1)\Theta(\tau_1). Each resulting object has volume Θ(Aτ1)\Theta(A\tau_1), so their total volume is Ω(A∑kMSTklog⁡n)\Omega\left(\frac{A\sum_k\mathrm{MST}_k}{\log n}\right). If they were disjoint, their union would already give the desired lower bound, up to this logarithmic factor. They may overlap, but we argue that we can select a large subset and partition it into groups so that objects from different groups have disjoint interiors. Within each group, we apply a common linear transformation that stretches and shears the objects so that they roughly correspond to tubes in the transformed space. Intuitively, the tube directions are separated because any two objects either belong to different shadow classes or have distance at least τ1\tau_1 within the same class. We can now apply Theorem 4 within each group to show that there is little overlap, then transfer the volume bounds back to the original space and add them across the disjoint groups. Making this possible while retaining enough objects is our main technical contribution. The union lies in a constant enlargement of the container, so the Kakeya estimate gives, for every ε>0\varepsilon> 0,

A∑kMSTk=Oε(nε)OPTvol.A \sum_k \mathrm{MST}_k = O_{\varepsilon}(n^{\varepsilon}) \mathrm{OPT}_{\mathrm{vol}}.

Together with the upper bound, this gives the approximation guarantee. Stronger tube estimates give the polylogarithmic guarantees for the same algorithm.

Packing bc-parallelepipeds

We first describe the packing algorithm for a special family of parallelepipeds. § 4 reduces general convex polyhedra to such families. Each object has one edge parallel to the xx-axis, one edge parallel to the xyxy-plane, and one edge with a positive zz-component (see Figure 1).

A bc-parallelepiped and its projections onto the xy- and yz-planes

Figure 1. A bcbc-parallelepiped with ki=2k_i = 2, translated so that one vertex is at the origin (a), and its projections onto the xyxy-plane (b) and the yzyz-plane (c). The edges are A=(ai,0,0)A = (a_i, 0, 0), Ui=(ui,b,0)U_i = (u_i, b, 0), and Vi=(vi,kib,c)V_i = (v_i, k_i b, c). Objects with the same kik_i share the yzyz-projection.

We fix the yy-component bb of the second edge, and the zz-component cc of the third edge. The components uiu_i, viv_i, and kik_i of the second and third edges describe how the objects slant. More precisely, for fixed b,c>0b, c > 0, a bcbc-parallelepiped is a translate of

Pi={λ1(ai00)+λ2(uib0)+λ3(vikibc):λ1,λ2,λ3∈[−12,12]},P_i = \left\{ \lambda_1 \begin{pmatrix} a_i \\ 0 \\ 0 \end{pmatrix} + \lambda_2 \begin{pmatrix} u_i \\ b \\ 0 \end{pmatrix} + \lambda_3 \begin{pmatrix} v_i \\ k_i b \\ c \end{pmatrix} : \lambda_1,\lambda_2,\lambda_3 \in\left[-\frac{1}{2},\frac{1}{2}\right] \right\},

where ai>0a_i > 0, ui,vi∈Ru_i,v_i \in\mathbb{R} and ki∈Zk_i \in\mathbb{Z} are the four free parameters. Here aia_i is the length of the first edge, uiu_i and viv_i are the xx-components of the second and third edges, while kik_i specifies the third edge’s yy-component in multiples of bb. Objects sharing (b,c)(b,c) form a type, and object ii has volume aibca_i bc. We consider a single type with nn objects P1,…,PnP_1,\ldots,P_n. We assume that each object fits individually in the unit cube, or equivalently that

ai+∣ui∣+∣vi∣≤1,(1+∣ki∣)b≤1,c≤1.a_i+\lvert u_i\rvert+\lvert v_i\rvert\le1,\qquad(1+\lvert k_i\rvert)b\le1,\qquad c\le1.

The projection onto the yzyz-plane maps the three edges to (0,0)(0,0), (b,0)(b,0), and (kib,c)(k_i b,c), so the shadow of PiP_i is the parallelogram spanned by (b,0)(b,0) and (kib,c)(k_i b,c); see Figure 1(c). Within a type, this shadow depends only on kik_i, not on uiu_i and viv_i. Objects with ki=kk_i=k form shadow class kk.

One way to pack objects of the same shadow class is to translate them only along the xx-axis, so that their shadows coincide. The distance required between two such objects is determined by their shears uiu_i and viv_i. For two objects ii and jj, let

d(i,j)=∣ui−uj∣+∣vi−vj∣.d(i,j)=\lvert u_i-u_j\rvert+\lvert v_i-v_j\rvert.

The following lemma shows that their centres then need to be exactly ai+aj2+d(i,j)2\frac{a_i+a_j}{2}+\frac{d(i,j)}{2} apart.

Lemma 5. Let ii and jj be objects of the same shadow class. Then PiP_i and Pj+(h,0,0)P_j+(h,0,0) have disjoint interiors if and only if ∣h∣≥ai+aj2+d(i,j)2\lvert h\rvert\ge\frac{a_i+a_j}{2}+\frac{d(i,j)}{2}.

Proof. The common shadow of the shadow class consists of the points (bs+kbt,ct)(bs+kbt,ct) with s,t∈[−12,12]s,t\in\left[-\frac{1}{2},\frac{1}{2}\right]. The point λ1(ai,0,0)+λ2(ui,b,0)+λ3(vi,kib,c)\lambda_1(a_i,0,0)+\lambda_2(u_i,b,0)+\lambda_3(v_i,k_i b,c) of PiP_i lies above (bs+kbt,ct)(bs+kbt,ct) exactly when λ2=s\lambda_2=s and λ3=t\lambda_3=t. Hence, above this point, PiP_i and Pj+(h,0,0)P_j+(h,0,0) occupy the xx-intervals uis+vit+[−ai2,ai2]u_i s+v_i t+\left[-\frac{a_i}{2},\frac{a_i}{2}\right] and h+ujs+vjt+[−aj2,aj2]h+u_j s+v_j t+\left[-\frac{a_j}{2},\frac{a_j}{2}\right]. These intervals overlap in an interval of positive length exactly when the distance between their midpoints is less than ai+aj2\frac{a_i+a_j}{2}. The distance between their midpoints is ∣δij(s,t)∣\lvert\delta_{ij}(s,t)\rvert, where

δij(s,t)=h+(uj−ui)s+(vj−vi)t.\delta_{ij}(s,t)=h+(u_j-u_i)s+(v_j-v_i)t.

As ss and tt range over [−12,12]\left[-\frac{1}{2},\frac{1}{2}\right], the values of δij\delta_{ij} form the interval [h−d(i,j)2,h+d(i,j)2]\left[h-\frac{d(i,j)}{2},h+\frac{d(i,j)}{2}\right], with the endpoints attained at corners.

If ∣h∣≥ai+aj2+d(i,j)2\lvert h\rvert\ge\frac{a_i+a_j}{2}+\frac{d(i,j)}{2}, then either h−d(i,j)2≥ai+aj2h-\frac{d(i,j)}{2}\ge\frac{a_i+a_j}{2} or h+d(i,j)2≤−ai+aj2h+\frac{d(i,j)}{2}\le-\frac{a_i+a_j}{2}, so ∣δij∣≥ai+aj2\lvert\delta_{ij}\rvert\ge\frac{a_i+a_j}{2} everywhere. Hence, above every point of the shadow, the two intervals share at most an endpoint, so the interiors of the objects do not overlap.

Conversely, let ∣h∣<ai+aj2+d(i,j)2\lvert h\rvert<\frac{a_i+a_j}{2}+\frac{d(i,j)}{2}. The value of the interval closest to 0 has absolute value max⁡{∣h∣−d(i,j)2,0}<ai+aj2\max\{\lvert h\rvert-\frac{d(i,j)}{2},0\}<\frac{a_i+a_j}{2}, so ∣δij(s,t)∣<ai+aj2\lvert\delta_{ij}(s,t)\rvert<\frac{a_i+a_j}{2} for some s,ts,t with ∣s∣,∣t∣<12\lvert s\rvert,\lvert t\rvert<\frac{1}{2}. Above the corresponding interior point of the shadow, the two xx-intervals overlap in an interval of positive length, whose interior points are interior points of both objects. □

Thus, placing objects with similar ui,viu_i,v_i-values consecutively saves space. We write MST⁡k\operatorname{MST}_k for the minimum spanning tree weight of shadow class kk under dd.

The algorithm

The algorithm places the objects in three steps, illustrated in Figure 2 and summarized in Algorithm 1.

Figure 2. Packing abcabc-parallelepipeds of varying thickness aia_i, with colors indicating shadow classes. (a) Each class is lined up along the xx-axis in an MST-based order; the black lines pierce each line above the centre of its shadow. (b) The lines are cut into blocks, which are placed in a fan. The dashed box is the bounding box.

(1) Order each shadow class. We order the class by the classic MST-based 2-approximation for metric Hamiltonian paths; consecutive objects in this order have total distance at most 2MST⁡k2\operatorname{MST}_k. We translate object ii by (xi,0,0)(x_i,0,0), where the first object gets the offset xi=0x_i=0, and every later object gets the offset xj=xi+ai+aj2+d(i,j)2x_j=x_i+\frac{a_i+a_j}{2}+\frac{d(i,j)}{2}, where ii is its predecessor, so consecutive objects then touch without overlapping.

(2) Cut the classes into blocks. Objects of the same class with the same value of ⌊xi⌋\lfloor x_i\rfloor form a block, and we translate each block by (−⌊xi⌋,0,0)(-\lfloor x_i\rfloor,0,0), so that all offsets lie in [0,1)[0,1). Since ai+∣ui∣+∣vi∣≤1a_i+|u_i|+|v_i|\le1, every object lies within xx-distance 1/21/2 of its offset, so every block lies in the slab −1/2≤x≤3/2-1/2\le x\le3/2, and no object is cut. Without this step, a single long shadow class could determine the xx-extent of the whole packing. For a visualization, compare the two subfigures of Figure 2, where on the right, the turquoise shadow class has been cut into blocks.

(3) Place the blocks in a fan. We number the blocks 1,…,N1,\ldots,N in order of increasing shadow class kk, breaking ties arbitrarily, and translate the ℓ\ell-th block, of class kk, by (0,(ℓ−1+k/2)b,0)(0,(\ell-1+k/2)b,0), so that the bottom edges of the block shadows lie next to each other. Since the slants increase from left to right, the shadows spread apart as zz increases and never cross.

The next lemma ensures that objects in different blocks do not overlap.

Lemma 6. Let PiP_i and PjP_j be objects with ki≤kjk_i\le k_j, and let ℓi<ℓj\ell_i<\ell_j be integers. Then, for all xi,xj∈Rx_i,x_j\in\mathbb{R}, the objects Pi+(xi,(ℓi−1+ki/2)b,0)P_i+(x_i,(\ell_i-1+k_i/2)b,0) and Pj+(xj,(ℓj−1+kj/2)b,0)P_j+(x_j,(\ell_j-1+k_j/2)b,0) have disjoint interiors.

Algorithm 1 Packing bcbc-parallelepipeds

  1. for each nonempty shadow class kk do

  2. Order the class as i1,…,iri_1,\ldots,i_r by the MST-based 2-approximation.

  3. Set xi1←0x_{i_1}\leftarrow0 and xij←xij−1+aij−1+aij2+d(ij−1,ij)2x_{i_j}\leftarrow x_{i_{j-1}}+\frac{a_{i_{j-1}}+a_{i_j}}{2}+\frac{d(i_{j-1},i_j)}{2} for j=2,…,rj=2,\ldots,r.

  4. end for

  5. Number the blocks, i.e. the distinct pairs (ki,⌊xi⌋)(k_i,\lfloor x_i\rfloor), as 1,…,N1,\ldots,N in order of increasing kik_i.

  6. Let ℓi\ell_i be the number of the block containing PiP_i.

  7. Translate each PiP_i by (xi−⌊xi⌋,(ℓi−1+ki/2)b,0)(x_i-\lfloor x_i\rfloor,(\ell_i-1+k_i/2)b,0).

  8. return these translations and the axis-parallel bounding box.

Proof. At height z=ctz=ct, where −12≤t≤12-\frac{1}{2}\le t\le\frac{1}{2}, the two objects have yy-coordinates in (ℓi−1)b+kib(t+12)+[−b2,b2](\ell_i-1)b+k_i b(t+\frac{1}{2})+[-\frac{b}{2},\frac{b}{2}] and (ℓj−1)b+kjb(t+12)+[−b2,b2](\ell_j-1)b+k_j b(t+\frac{1}{2})+[-\frac{b}{2},\frac{b}{2}], respectively. The second interval starts where the first ends or later, because the difference of their midpoints is (ℓj−ℓi)b+(kj−ki)b(t+12)≥b(\ell_j-\ell_i)b+(k_j-k_i)b(t+\frac{1}{2})\ge b.

Lemma 7. In O(nlog⁡n)O(n\log n) time, Algorithm 1 returns a translational packing of P1,…,PnP_1,\ldots,P_n in an axis-parallel box of volume

O(∑iaibc+bc∑kMST⁡k+c).O\left(\sum_i a_i b c+bc\sum_k \operatorname{MST}_k+c\right).

Proof. We first show that no two objects overlap. Consider two objects i≠ji\ne j, labelled so that ℓi≤ℓj\ell_i\le\ell_j. If they lie in the same block, their translations differ only in the xx-coordinate, by xj−xix_j-x_i, and we may assume that ii comes before jj in their class. The distance dd is the ℓ1\ell_1-distance between the points (ui,vi)(u_i,v_i), so the triangle inequality gives xj−xi≥ai+aj2+d(i,j)2x_j-x_i\ge\frac{a_i+a_j}{2}+\frac{d(i,j)}{2}, and Lemma 5 applies. If they lie in different blocks, then ℓi<ℓj\ell_i<\ell_j and hence ki≤kjk_i\le k_j, so Lemma 6 applies.

Next, we bound the volume. The offsets of class kk lie in [0,Ak+MST⁡k][0,A_k+\operatorname{MST}_k], where AkA_k is the sum of the aia_i in the class, so the class produces at most Ak+MST⁡k+1A_k+\operatorname{MST}_k+1 blocks. Since ∣k∣b≤1|k|b\le1, at most 1+2/b1+2/b classes are nonempty, so the total number NN of blocks satisfies

Nb≤∑iaib+b∑kMST⁡k+b(1+2b)≤3+∑iaib+b∑kMST⁡k.Nb\le\sum_i a_i b+b\sum_k\operatorname{MST}_k+b\left(1+\frac{2}{b}\right)\le3+\sum_i a_i b+b\sum_k\operatorname{MST}_k.

The final packing lies in [−12,12]×[−1−b2,(N−12)b+1]×[−c2,c2][-\frac{1}{2},\frac{1}{2}]\times[-1-\frac{b}{2},(N-\frac{1}{2})b+1]\times[-\frac{c}{2},\frac{c}{2}], since the ℓ\ell-th block has yy-coordinates within (1+∣k∣)b/2(1+|k|)b/2 of (ℓ−1+k/2)b(\ell-1+k/2)b and ∣k∣b≤1|k|b\le1. Multiplying the side lengths proves the bound.

Finally, we bound the running time. The distance dd is the ℓ1\ell_1-distance between the points (ui,vi)(u_i,v_i), so a minimum spanning tree of a class with rr objects can be computed in O(rlog⁡r)O(r\log r) time [25]. Finally, sorting the at most nn blocks by shadow class takes O(nlog⁡n)O(n\log n) time.

Bounding the spanning-tree cost

Since ∑iaibc≤1\sum_i a_i bc\le1 and c≤1c\le1 for families that fit in the unit cube, it remains to bound bc∑kMST⁡kbc\sum_k\operatorname{MST}_k. For a shadow class kk, let GkG_k be the complete graph on its objects with edge weights d(i,j)d(i,j). For τ>0\tau>0, define

Gk(τ)=(V(Gk),{e∈E(Gk):d(e)≤τ}).G_k(\tau)=\left(V(G_k),\{e\in E(G_k):d(e)\le\tau\}\right).

where d(e)d(e) is the weight of edge ee, and let ck(τ)c_k(\tau) be its number of connected components. Since each object fits in the unit cube, ∣ui∣+∣vi∣≤1|u_i|+|v_i|\le1, so all edge weights are at most 2. We have the identity

MST⁡k=∫02(ck(τ)−1) dτ.(2)\operatorname{MST}_k=\int_0^2(c_k(\tau)-1)\,\mathrm{d}\tau. \tag*{(2)}

Indeed, a minimum spanning tree has exactly ck(τ)−1c_k(\tau)-1 edges of weight greater than τ\tau: deleting these edges leaves a forest whose trees exactly correspond to the components of Gk(τ)G_k(\tau). Each tree lies in one component, since its edges belong to Gk(τ)G_k(\tau). Conversely, if there are two or more trees in the same connected component, then there is also an edge xyxy of Gk(τ)G_k(\tau) joining two such trees. Hence, the path from xx to yy in the minimum spanning tree would contain a deleted edge, which is heavier than xyxy. Exchanging the two edges would give a lighter spanning tree. An edge of weight ww of the minimum spanning tree is therefore counted for 0≤τ<w0\le\tau<w and contributes exactly ww to the integral. This is a continuous version of an identity of Chazelle, Rubinfeld, and Trevisan [12 Claim 5].

Summing over all shadow classes and exchanging sum and integral gives

∑kMST⁡k=∫02∑k(ck(τ)−1) dτ.\sum_k \operatorname{MST}_k=\int_0^2\sum_k(c_k(\tau)-1)\,\mathrm{d}\tau.

The point of this identity is that it replaces the spanning trees, which mix all scales, by component counts at single scales. At a fixed scale, many components mean many objects whose shears are pairwise far apart, and a packing in the unit cube cannot contain too many such objects, as we show below. It therefore suffices to bound ∑kck(τ)\sum_k c_k(\tau), the total number of components at scale τ\tau, for every τ\tau. We bound this sum for all shadow classes together, since bounding each class separately would lose a factor of the number of classes.

Fix τ\tau and choose one representative from each component of every Gk(τ)G_k(\tau). These ∑kck(τ)\sum_k c_k(\tau) objects still fit in the unit cube, and two representatives of the same shadow class satisfy d(i,j)>τd(i,j)>\tau, since otherwise an edge would join their components. The following theorem, the geometric lower bound at the core of our analysis, therefore bounds ∑kck(τ)\sum_k c_k(\tau); we prove it in § 3.

Theorem 8 (Lower Bound). For every ε>0\varepsilon>0, there exists a constant Cε>0C_\varepsilon>0 such that the following holds. Let P\mathcal{P} be a family of at most nn bcbc-parallelepipeds that can be packed by translations into the unit cube. If, for some 0<τ≤20<\tau\le2, we have d(Pi,Pj)>τd(P_i,P_j)>\tau for every pair of distinct objects Pi,Pj∈PP_i,P_j\in\mathcal{P} with ki=kjk_i=k_j, then

∣P∣≤Cεnεbcτ.|\mathcal{P}|\le C_\varepsilon\frac{n^\varepsilon}{bc\tau}.

Note that the theorem holds for arbitrary separated families and is not specific to the representatives. They do, however, satisfy its assumptions, so we can apply it to them in particular:

  1. they are bcbc-parallelepipeds of a single type;

  1. they form a subfamily of the input, so they can be packed by translations into the unit cube;

  1. any two representatives with ki=kjk_i=k_j lie in different components of Gki(τ)G_{k_i}(\tau), so d(Pi,Pj)>τd(P_i,P_j)>\tau.

Hence, for every 0<τ≤20<\tau\le2,

∑kck(τ)≤Cεnεbcτ.\sum_k c_k(\tau)\le C_\varepsilon\frac{n^\varepsilon}{bc\tau}.

It remains to integrate over τ\tau from 0 to 2. Small scales τ<1/n\tau< 1/n are handled by the trivial bound of nn components, and larger scales by Theorem 8.

Lemma 9. If P1,…,PnP_1,\ldots,P_n are bcbc-parallelepipeds that admit a translational packing into the unit cube, then, for every ε>0\varepsilon> 0,

bc∑kMST⁡k=Oε(nε).bc\sum_k \operatorname{MST}_k = O_{\varepsilon}(n^{\varepsilon}).

Proof. Choosing one object from each component of the graphs Gk(τ)G_k(\tau) gives a family satisfying Theorem 8, so ∑kck(τ)≤min⁡{n,Cεnεbcτ}\sum_k c_k(\tau) \le\min\left\{n,\frac{C_{\varepsilon}n^{\varepsilon}}{bc\tau}\right\}. The MST identity (2), split at 1/n1/n, now gives

bc∑kMST⁡k=bc∫02∑k(ck(τ)−1) dτ≤bc∫01/n∑kck(τ) dτ+bc∫1/n2∑kck(τ) dτ≤bc∫01/nn dτ+∫1/n2Cεnετ dτ=bc+Cεnεln⁡(2n)≤1+Cεnεln⁡(2n).\begin{aligned} bc\sum_k \operatorname{MST}_k &=bc\int_0^2\sum_k(c_k(\tau)-1)\,d\tau\\ &\le bc\int_0^{1/n}\sum_k c_k(\tau)\,d\tau+bc\int_{1/n}^2\sum_k c_k(\tau)\,d\tau\\ &\le bc\int_0^{1/n}n\,d\tau+\int_{1/n}^2\frac{C_{\varepsilon}n^{\varepsilon}}{\tau}\,d\tau\\ &=bc+C_{\varepsilon}n^{\varepsilon}\ln(2n)\\ &\le1+C_{\varepsilon}n^{\varepsilon}\ln(2n). \end{aligned}

Finally, we absorb the logarithm and rescale ε\varepsilon.

Together with Lemma 7, and since ∑iaibc≤1\sum_i a_i bc\le1 and c≤1c\le1, this shows that if P1,…,PnP_1,\ldots,P_n admit a translational packing into the unit cube, then Algorithm 1 packs them into a box of volume Oε(nε)O_{\varepsilon}(n^{\varepsilon}). In § 4, we scale a general instance so that an optimal container becomes the unit cube and reduce it to this case at the cost of constant and polylogarithmic factors, which gives the approximation ratio no(1)n^{o(1)} of Theorem 1.

The lower bound

In this section, we prove Theorem 8 by a purely geometric argument.

We fix a family P\mathcal{P} satisfying its assumptions, so that d(i,j)>τd(i,j)>\tau for any two distinct objects i,ji,j with ki=kjk_i=k_j, and fix a packing in [0,1]3[0,1]^3. Throughout the rest of this section, PiP_i denotes the placed object and pip_i its center. Its parameters satisfy

ai+∣ui∣+∣vi∣≤1,(1+∣ki∣)b≤1,c≤1.a_i+|u_i|+|v_i|\le1,\qquad(1+|k_i|)b\le1,\qquad c\le1.

Object ii has volume aibca_i bc, so volume counting shows that at most 100/(bcτ)100/(bc\tau) objects have ai≥τ/100a_i\ge\tau/100. For objects with ai≪τa_i\ll\tau, however, volume counting is far too weak. We therefore thicken these objects in the xx-direction so that each has volume roughly bcτbc\tau, as needed for the desired counting bound. Thickening may introduce overlaps, but if we can keep these small, the volume of the union will still bring us close to that bound.

We first divide the objects into slope groups and construct thickened bodies that can overlap only within the same group, while retaining a constant fraction of the objects. Within each group, the bodies have similar shapes but point in different directions. We apply a common linear transformation so that they contain comparable tubes, and use Kakeya to bound their union volume in the transformed space. Dividing by the absolute determinant of the transformation then gives a volume bound in the original space. Since bodies from different groups are disjoint, these bounds add to give the desired counting estimate.

Auxiliary bodies By volume counting, at most 100/(bcτ)100/(bc\tau) objects have ai≥τ/100a_i \ge\tau/100, so it suffices to bound the number of objects with ai<τ/100a_i < \tau/100, and we consider only these from now on; let P′P' be the family of these objects. We cut the real line into intervals of length τ/100\tau/100 and label them 1,2,…,10,1,2,…,10,…1,2,\ldots,10,1,2,\ldots,10,\ldots from left to right.

Partitioning the offsets $u_i$ into slope groups

Figure 3. Partitioning the offsets uiu_i into slope groups. Each point represents one object; the highlighted intervals illustrate retaining label 3.

We then retain only the objects whose uiu_i-values lie in intervals of the label that contains the most uiu_i-values. Objects whose uiu_i-values lie in the same interval form a slope group. This retains at least a tenth of the objects, so it suffices to bound the number of retained objects: any such bound also bounds ∣P∣|P|, up to a factor of 10. Moreover, two intervals with the same label are always separated by a gap of at least 9τ/1009\tau/100.

For every retained object, define the auxiliary body

Qi=pi+{λ1(τ/10000)+λ214(uib0)+λ3(vikibc):λ1,λ2,λ3∈[−12,12]}.(3)Q_i=p_i+\left\{\lambda_1\begin{pmatrix}\tau/100\\0\\0\end{pmatrix}+\lambda_2\frac{1}{4}\begin{pmatrix}u_i\\b\\0\end{pmatrix}+\lambda_3\begin{pmatrix}v_i\\k_i b\\c\end{pmatrix}:\lambda_1,\lambda_2,\lambda_3\in\left[-\frac{1}{2},\frac{1}{2}\right]\right\}. \tag*{(3)}

Thus QiQ_i has the same center as PiP_i, a first edge of length τ/100\tau/100, and one quarter of its second edge. In each plane parallel to the xyxy-plane, this is precisely the shortening and thickening shown in Figure 4. Its volume is bcτ/400bc\tau/400.

Three schematic panels showing shortened and thickened objects, the proof of Lemma 10, and overlap within slope groups

Figure 4. Intersections of the objects with a plane parallel to the xyxy-plane. (a) Original objects Pi,PjP_i, P_j and their thickened middle portions Qi,QjQ_i, Q_j. (b) If QiQ_i and QjQ_j share a point pp, the center lines of PiP_i and PjP_j (dashed) are less than τ/100\tau/100 apart at pp, so they cross at a point qq less than b/9b/9 from pp in yy, which lies inside both parallelograms, leading to a contradiction. (c) Grey objects are discarded, and overlaps occur only within a slope group.

Lemma 10. Auxiliary bodies from different retained slope groups have disjoint interiors. Every QiQ_i lies in [−τ/200,1+τ/200]×[0,1]2[-\tau/200,1+\tau/200]\times[0,1]^2.

Proof. Suppose, for a contradiction, that QiQ_i and QjQ_j from different retained groups share an interior point pp. In the plane through pp parallel to the xyxy-plane, each auxiliary body is a thickened middle quarter of the corresponding parallelogram section of PiP_i or PjP_j; see Figure 4(a). The center lines of the original sections have slopes ui/bu_i/b and uj/bu_j/b. Since pp lies in both thickened sections, the lines are less than τ/100\tau/100 apart in the xx-direction at pp’s yy-coordinate. Their slopes differ by ∣ui−uj∣/b≥9τ/(100b)|u_i-u_j|/b\ge9\tau/(100b), so they intersect at a point qq within a yy-distance of b/9b/9 from pp; see Figure 4(b).

By (3), shortening retains the middle quarter of each original section in the yy-direction, so pp is at least 3b/83b/8 from either end in that direction. Since b/9<3b/8b/9<3b/8, the intersection point qq lies inside both original sections and is therefore an interior point of both PiP_i and PjP_j. Their interiors thus overlap, a contradiction to the assumption that the original objects form a packing with pairwise disjoint interiors. Finally, shortening preserves containment in the unit cube, and thickening adds less than τ/200\tau/200 on either side in the xx-direction, proving the stated containment.

Finding Tubes For a retained interval II with midpoint uIu_I, define

TI(x,y,z)=(bx−uIy,τy,z/c)T_I(x,y,z)=(bx-u_Iy,\tau y,z/c)

which has ∣det⁡TI∣=bτ/c|\det T_I|=b\tau/c. Applying this map to (3), gives

TI(Qi)=TI(pi)+{λ1(bτ/10000)+λ24(b(ui−uI)bτ0)+λ3(b(vi−kiuI)kibτ1):λ1,λ2,λ3∈[−12,12]}.(4)T_I(Q_i)=T_I(p_i)+\left\{\lambda_1\begin{pmatrix}b\tau/100\\0\\0\end{pmatrix}+\frac{\lambda_2}{4}\begin{pmatrix}b(u_i-u_I)\\b\tau\\0\end{pmatrix}+\lambda_3\begin{pmatrix}b(v_i-k_i u_I)\\k_i b\tau\\1\end{pmatrix}:\lambda_1,\lambda_2,\lambda_3\in\left[-\frac{1}{2},\frac{1}{2}\right]\right\}. \tag*{(4)}

Let DiD_i denote the third edge vector in (4), with unit direction di=Di/∥Di∥d_i = D_i/\lVert D_i\rVert, and set δ=bτ/1000\delta= b\tau/1000. The following lemma shows that each 2TI(Qi)2T_I(Q_i) contains a tube of radius δ\delta in direction did_i, with the tube directions pairwise δ\delta-separated within each retained slope group.

Lemma 11. Within each retained slope group, every 2TI(Qi)2T_I(Q_i) contains the tube Si=Tδ(di,2TI(pi))S_i = T_\delta(d_i,2T_I(p_i)), and the unoriented angle between did_i and djd_j is at least δ\delta for each i≠ji \ne j.

Proof. The first two edge vectors in (4) span a parallelogram in the xyxy-plane of xx-width bτ/100b\tau/100 and yy-height bτ/4b\tau/4. Since ui∈Iu_i \in I, the shear satisfies

∣b(ui−uI)4∣≤bτ800.\left|\frac{b(u_i-u_I)}{4}\right| \le\frac{b\tau}{800}.

This bound on the shear implies that the parallelogram contains the disk BB centered at the origin with radius bτ/400b\tau/400; see Figure 5. Moreover, 1≤∥Di∥≤41 \le\lVert D_i\rVert\le4 follows from ∣vi∣≤1|v_i| \le1, ∣ki∣b≤1|k_i|b \le1, ∣uI∣≤1.01|u_I| \le1.01, and τ≤2\tau\le2. After translating so that TI(pi)=0T_I(p_i) = 0, (4) gives

Schematic transformation from P to Q and then to the transformed object T_I(Q), showing generating edges and a disk

Figure 5. The disk in TI(Q)T_I(Q) has radius Θ(bτ)\Theta(b\tau) and yields a tube along the object. Arrows show the generating edges, labeled with their xyxy-components; the drawings are schematic and not to scale.

TI(Qi)⊇{q+λDi:q∈B, ∣λ∣≤12}.T_I(Q_i) \supseteq\left\{q+\lambda D_i:q\in B,\ |\lambda|\le\frac{1}{2}\right\}.

To prove the tube containment, it suffices to show that TI(Qi)T_I(Q_i) contains 12Tδ(di,0)\frac{1}{2}T_\delta(d_i,0), the δ/2\delta/2-neighbourhood of the segment {tdi:∣t∣≤14}\{td_i:|t|\le\frac{1}{4}\}. Any point in this set can be written as tdi+etd_i+e, where ∣t∣≤14|t|\le\frac{1}{4} and ∥e∥<δ/2\lVert e\rVert<\delta/2. Writing eze_z for the zz-coordinate of ee, we have

tdi+e=(e−ezDi)+(t∥Di∥+ez)Di.td_i+e=(e-e_zD_i)+\left(\frac{t}{\lVert D_i\rVert}+e_z\right)D_i.

Because DiD_i has zz-coordinate 11, the vector e−ezDie-e_zD_i lies in the xyxy-plane and satisfies

∥e−ezDi∥≤∥e∥+∣ez∣∥Di∥<5δ2=bτ400.\lVert e-e_zD_i\rVert\le\lVert e\rVert+|e_z|\lVert D_i\rVert<\frac{5\delta}{2}=\frac{b\tau}{400}.

Thus e−ezDi∈Be-e_zD_i\in B, while the coefficient of DiD_i has absolute value at most 14+δ2≤12\frac{1}{4}+\frac{\delta}{2}\le\frac{1}{2}. The point therefore lies in TI(Qi)T_I(Q_i), proving the claimed containment.

For the angular separation, take distinct objects i,ji,j in the same group. If ki≠kjk_i\ne k_j, the second coordinates of DiD_i and DjD_j differ by at least bτb\tau. If ki=kjk_i=k_j, the separation assumption and ∣ui−uj∣<τ/100|u_i-u_j|<\tau/100 give ∣vi−vj∣>99τ/100|v_i-v_j|>99\tau/100, so their first coordinates differ by more than 99bτ/10099b\tau/100. In either case,

∥Di−Dj∥≥99bτ100.\lVert D_i-D_j\rVert\ge\frac{99b\tau}{100}.

Let φ\varphi be the unoriented angle between did_i and djd_j, and consider the triangle with vertices 00, DiD_i, and DjD_j. Its area is 12∥Di∥∥Dj∥sin⁡φ≤8sin⁡φ\frac{1}{2}\lVert D_i\rVert\lVert D_j\rVert\sin\varphi\le8\sin\varphi. The line through DiD_i and DjD_j lies in the plane z=1z=1, so its distance from the origin is at least 11 and the area is at least 12∥Di−Dj∥\frac{1}{2}\lVert D_i-D_j\rVert. Comparing these bounds gives

φ≥sin⁡φ≥∥Di−Dj∥16≥99bτ1600≥δ.\varphi\ge\sin\varphi\ge\frac{\lVert D_i-D_j\rVert}{16}\ge\frac{99b\tau}{1600}\ge\delta.

The volume bound

Fix a retained interval II containing nIn_I objects. By Lemma 11, the tubes SiS_i with ui∈Iu_i \in I have pairwise δ\delta-separated directions, so Theorem 4 applies with δ=bτ/1000≤1\delta=b\tau/1000 \le1. Using Si⊆2TI(Qi)S_i \subseteq2T_I(Q_i), vol⁡(Si)≥πδ2\operatorname{vol}(S_i) \ge\pi\delta^2, and ∣det⁡(2TI)∣=8bτ/c|\det(2T_I)|=8b\tau/c, we obtain

vol⁡(⋃ui∈IQi)=c8bτvol⁡(⋃ui∈I2TI(Qi))≥c8bτvol⁡(⋃ui∈ISi)≥c8bτ⋅δεCε∑ui∈Ivol⁡(Si)≥c8bτ⋅δεCεnIπδ2≥nIbcτδε3⋅106Cε.\begin{aligned} \operatorname{vol}\left(\bigcup_{u_i\in I}Q_i\right)=\frac{c}{8b\tau}\operatorname{vol}\left(\bigcup_{u_i\in I}2T_I(Q_i)\right)\ge\frac{c}{8b\tau}\operatorname{vol}\left(\bigcup_{u_i\in I}S_i\right) \\ &\ge\frac{c}{8b\tau}\cdot\frac{\delta^\varepsilon}{C_\varepsilon}\sum_{u_i\in I}\operatorname{vol}(S_i)\ge\frac{c}{8b\tau}\cdot\frac{\delta^\varepsilon}{C_\varepsilon}n_I\pi\delta^2\ge\frac{n_Ibc\tau\delta^\varepsilon}{3\cdot10^6C_\varepsilon}. \end{aligned}

By Lemma 10, the unions for distinct retained intervals have disjoint interiors and lie in a common box of volume 1+τ/100≤21+\tau/100\le2. Summing the preceding bound over the retained intervals therefore gives

2≥vol⁡(⋃retained iQi)=∑Ivol⁡(⋃ui∈IQi)≥∣P′∣bcτδε3⋅107Cε.2\ge\operatorname{vol}\left(\bigcup_{\text{retained }i}Q_i\right)=\sum_I\operatorname{vol}\left(\bigcup_{u_i\in I}Q_i\right)\ge\frac{|P'|bc\tau\delta^\varepsilon}{3\cdot10^7C_\varepsilon}.

where the sum runs over the retained intervals, which together contain at least ∣P′∣/10|P'|/10 objects. Rearranging this inequality gives

∣P′∣≤6⋅107Cεδ−εbcτ≤6⋅1010Cεn2εbcτ.|P'|\le6\cdot10^7C_\varepsilon\frac{\delta^{-\varepsilon}}{bc\tau}\le6\cdot10^{10}C_\varepsilon\frac{n^{2\varepsilon}}{bc\tau}.

where the last step assumes bτ≥n−2b\tau\ge n^{-2} and ε≤1\varepsilon\le1, so that δ−ε≤1000(bτ)−ε≤1000n2ε\delta^{-\varepsilon}\le1000(b\tau)^{-\varepsilon}\le1000n^{2\varepsilon}.

Otherwise, Theorem 8 holds trivially, since ∣P∣≤n<1/(bτ)≤1/(bcτ)|P|\le n<1/(b\tau)\le1/(bc\tau). Adding the at most 100/(bcτ)100/(bc\tau) objects with ai≥τ/100a_i\ge\tau/100 to the bound on P′P', replacing ε\varepsilon by ε/2\varepsilon/2, and absorbing the constants into CεC_\varepsilon proves Theorem 8.

Reduction to bcbc-parallelepipeds

In this section, we reduce general convex polyhedra K1,…,KnK_1,\ldots,K_n to the bcbc-parallelepipeds of § 2. § 4.1 constructs enclosures only a constant factor larger than the objects, with polylogarithmically many pairs (b,c)(b,c) defining the groups packed by Algorithm 1. § 4.2 gives the complete algorithm: we guess the dimensions of an optimal container, pack each group with Algorithm 1, handle very thin objects separately, and combine the packings into one box. Throughout, wr(K)w_r(K) denotes the width of a polyhedron KK in coordinate r∈{x,y,z}r\in\{x,y,z\}, and in § 4.1 we assume that all these widths are at most 11.

Enclosing each object

We can enclose each object in a parallelepiped that lies within a constant enlargement of the object; see Figure 6.

The enclosure of Lemma 12

Figure 6. The enclosure of Lemma 12. (a,b) Stretching B⊆C⊆3BB \subseteq C \subseteq\sqrt{3}B by AA gives E⊆F⊆3EE \subseteq F \subseteq\sqrt{3}E. (c) KK inside FF. (d) The section through the center: K⊆F⊆7KK \subseteq F \subseteq7K (dashed, not to scale).

Lemma 12. Let KK be a (full-dimensional) convex polyhedron. In polynomial time, we can find a parallelepiped FF, with edges (a,0,0)(a,0,0), (u,b,0)(u,b,0), and (v,q,c)(v,q,c), where a,b,c>0a,b,c>0, such that K⊆F⊆7KK\subseteq F\subseteq7K.

Proof. By the algorithmic version of John’s theorem [28] due to Grӧtschel, Lovász, and Schrijver [23], we can, after translating KK, compute in polynomial time an ellipsoid EE centered at the origin such that 14E⊆K⊆E\frac{1}{4}E \subseteq K \subseteq E.

An ellipsoid is a stretched ball. Stretching a cube around the ball in the same way gives a parallelepiped FF around EE, and since the ball lies in the cube and the cube lies in the ball enlarged by 3\sqrt{3}, we get E⊆F⊆3EE \subseteq F \subseteq\sqrt{3}E; see Figure 6(a,b). By rotating the cube before stretching, we can make the edges of FF have the form (a,0,0)(a,0,0), (u,b,0)(u,b,0), and (v,q,c)(v,q,c) with a,b,c>0a,b,c>0. To be precise, let TT be the non-singular linear transformation mapping the ball BB to the ellipsoid EE. We first pick a unit vector e1e_1 in the preimage T−1({(x,0,0):x∈R})T^{-1}(\{(x,0,0):x\in\mathbb{R}\}). Now T−1({(x,y,0):x,y∈R})T^{-1}(\{(x,y,0):x,y\in\mathbb{R}\}) has dimension 2, so there exists a vector e2e_2 orthogonal to e1e_1 mapping to this preimage. Finally, picking e3e_3 orthogonal to e1e_1 and e2e_2, the directions e1,e2,e3e_1,e_2,e_3 define the edges of the desired rotated cube.

Since 14E⊆K⊆E\frac{1}{4}E \subseteq K \subseteq E and KK contains the origin, this gives

K⊆E⊆F⊆3E⊆43K⊆7K.K \subseteq E \subseteq F \subseteq\sqrt{3}E \subseteq4\sqrt{3}K \subseteq7K.

For each KiK_i, let FiF_i be its enclosure from Lemma 12, with positive edge parameters ai,bi,cia_i,b_i,c_i and shears ui,vi,qiu_i,v_i,q_i. If the original objects fit in the unit cube, enlarging that packing by a factor of 7 allows each FiF_i to be placed inside the corresponding enlarged KiK_i, so the enclosures fit in a cube of side length 7 and satisfy

∑iaibici=∑ivol⁡(Fi)=O(1).\sum_i a_i b_i c_i = \sum_i \operatorname{vol}(F_i) = O(1).

Their edge coordinates are also O(1)O(1), since Fi⊆7KiF_i \subseteq7K_i and all input widths are at most 1.

We next reduce the number of choices for bb and cc by rounding bib_i and cic_i up to the next values in {1/n,2/n,4/n,…}\{1/n,2/n,4/n,\ldots\}, denoted BiB_i and CiC_i, while leaving aia_i unchanged. For now, we assume bi,ci≥1/nb_i,c_i \ge1/n and handle the remaining objects in the proof of Theorem 1.

We now replace FiF_i by a bcbc-parallelepiped PiP_i with first edge f1f_1 and (b,c)=(2Bi,Ci)(b,c)=(2B_i,C_i). Set βi=Bi/bi\beta_i=B_i/b_i and γi=Ci/ci\gamma_i=C_i/c_i, which satisfy 1≤βi,γi<21\le\beta_i,\gamma_i<2 because bi,ci≥1/nb_i,c_i\ge1/n. Scaling f2f_2 and f3f_3 by these factors gives the desired yy-component BiB_i and zz-component CiC_i, but the third edge’s yy-component γiqi\gamma_iq_i need not be an integer multiple of BiB_i. We therefore double the second edge and shift the third edge parallel to it; see Figure 7. Choose an integer kik_i nearest to γiqi/(2Bi)\gamma_iq_i/(2B_i) and set ti=γiqi/Bi−2kit_i=\gamma_iq_i/B_i-2k_i, so that ∣ti∣≤1|t_i|\le1. The resulting edges of PiP_i are

Rounding the $yz$-shadow of an enclosure

Figure 7. Rounding the yzyz-shadow (gray) of an enclosure. Doubling the base (blue) and moving the slanted side (red) parallel to it makes its yy-component a multiple of the new base. The new shadow contains the old one.

p1=f1=(ai00),p2=2βif2=(2βiui2Bi0),p3=γif3−tiβif2=(γivi−tiβiui2kiBiCi).p_1=f_1=\begin{pmatrix}a_i\\0\\0\end{pmatrix},\qquad p_2=2\beta_i f_2=\begin{pmatrix}2\beta_i u_i\\2B_i\\0\end{pmatrix},\qquad p_3=\gamma_i f_3-t_i\beta_i f_2=\begin{pmatrix}\gamma_i v_i-t_i\beta_i u_i\\2k_iB_i\\C_i\end{pmatrix}.

The yy-component of p3p_3 is kik_i times that of p2p_2, so PiP_i is an bcbc-parallelepiped as in § 2, with first edge of length aia_i and (b,c)=(2Bi,Ci)(b,c)=(2B_i,C_i).

Lemma 13. We have Ki⊆Pi⊆42KiK_i\subseteq P_i\subseteq42K_i.

Proof. By definition,

Fi={μ1f1+μ2f2+μ3f3:μ1,μ2,μ3∈[−12,12]},F_i=\left\{\mu_1f_1+\mu_2f_2+\mu_3f_3:\mu_1,\mu_2,\mu_3\in\left[-\frac12,\frac12\right]\right\},
Pi={λ1p1+λ2p2+λ3p3:λ1,λ2,λ3∈[−12,12]},P_i=\left\{\lambda_1p_1+\lambda_2p_2+\lambda_3p_3:\lambda_1,\lambda_2,\lambda_3\in\left[-\frac12,\frac12\right]\right\},

and scaling FiF_i by the factor of 6 gives

6Fi={μ1f1+μ2f2+μ3f3:μ1,μ2,μ3∈[−3,3]}.6F_i=\left\{\mu_1f_1+\mu_2f_2+\mu_3f_3:\mu_1,\mu_2,\mu_3\in[-3,3]\right\}.

Throughout, we use 1≤βi,γi<21\le\beta_i,\gamma_i<2, and ∣ti∣≤1|t_i|\le1.

To prove Fi⊆PiF_i\subseteq P_i, we express f1,f2,f3f_1,f_2,f_3 in terms of p1,p2,p3p_1,p_2,p_3:

f1=p1,f2=12βip2,f3=1γip3+ti2γip2.f_1=p_1,\qquad f_2=\frac{1}{2\beta_i}p_2,\qquad f_3=\frac{1}{\gamma_i}p_3+\frac{t_i}{2\gamma_i}p_2.

Hence a point μ1f1+μ2f2+μ3f3\mu_1f_1+\mu_2f_2+\mu_3f_3 of FiF_i equals

μ1p1+(μ22βi+tiμ32γi)p2+μ3γip3,\mu_1p_1+\left(\frac{\mu_2}{2\beta_i}+\frac{t_i\mu_3}{2\gamma_i}\right)p_2+\frac{\mu_3}{\gamma_i}p_3,

and since ∣μ1∣,∣μ2∣,∣μ3∣≤12|\mu_1|,|\mu_2|,|\mu_3|\le\frac12, these coefficients are at most 12\frac12, 14+14\frac14+\frac14, and 12\frac12 in absolute value. So the point lies in PiP_i.

To show Pi⊆42KiP_i\subseteq42K_i, we first show Pi⊆6FiP_i\subseteq6F_i. Note that a point λ1p1+λ2p2+λ3p3\lambda_1p_1+\lambda_2p_2+\lambda_3p_3 of PiP_i, with ∣λ1∣,∣λ2∣,∣λ3∣≤12|\lambda_1|,|\lambda_2|,|\lambda_3|\le\frac12, equals

λ1f1+βi(2λ2−tiλ3)f2+γiλ3f3.\lambda_1f_1+\beta_i(2\lambda_2-t_i\lambda_3)f_2+\gamma_i\lambda_3f_3.

The coefficients of f1,f2,f3f_1,f_2,f_3 have absolute values at most 12\frac12, less than 2⋅32=32\cdot\frac32=3, and less than 2⋅12=12\cdot\frac12=1, respectively, so the point lies in 6Fi6F_i. Together with Lemma 12, this gives Pi⊆6Fi⊆42KiP_i\subseteq6F_i\subseteq42K_i.

Objects with the same rounded pair (Bi,Ci)(B_i,C_i) form a type, giving O(log⁡2n)O(\log^2 n) types since both parameters are rounded in powers of two between 1/n1/n and a constant. Moreover, Pi⊆42KiP_i \subseteq42K_i by Lemma 13, so the PiP_i have coordinate widths O(1)O(1).

Lemma 14. Suppose that K1,…,KnK_1,\ldots,K_n can be packed into the unit cube. Then, for each type, Algorithm 1 packs the PiP_i of this type into a box of volume Oε(nε)O_\varepsilon(n^\varepsilon).

Proof. Enlarging a packing of the KiK_i in the unit cube by a factor of 4242 allows us to place each PiP_i inside the corresponding enlarged KiK_i, since Pi⊆42KiP_i \subseteq42K_i by Lemma 13, giving a packing in a cube of side 4242. After scaling by 1/421/42, the PiP_i of each type fit into the unit cube, so Lemmas 7 and 9, together with ∑iaibc≤1\sum_i a_i bc \le1 and c≤1c \le1, give a packing of volume Oε(nε)O_\varepsilon(n^\varepsilon). Scaling back multiplies the volume by 42342^3.

Packing general convex polyhedra

Since we do not know the dimensions of an optimal container, we try several candidates. For r∈{x,y,z}r \in\{x,y,z\}, let Wr=max⁡iwr(Ki)W_r=\max_i w_r(K_i) be the largest width of an input object in coordinate rr, and let Lr∗L_r^* be the corresponding side length of an optimal container. Then

Wr≤Lr∗≤nWrfor r∈{x,y,z}.W_r \le L_r^* \le nW_r \qquad\text{for } r \in\{x,y,z\}.

The first inequality holds because every object fits into the container.

For the second, stacking all bounding boxes along one axis gives Lx∗Ly∗Lz∗≤nWxWyWzL_x^*L_y^*L_z^* \le nW_xW_yW_z, which yields Lr∗≤nWrL_r^* \le nW_r using the lower bounds in the other two coordinates. We therefore try the O(log⁡3n)O(\log^3 n) candidate containers with side lengths Lr∈{2jWr:0≤j≤⌈log⁡2n⌉}L_r \in\{2^jW_r : 0 \le j \le\lceil\log_2 n\rceil\}. At least one candidate satisfies Lr∗≤Lr<2Lr∗L_r^* \le L_r < 2L_r^* in every coordinate. For each candidate, we scale coordinate rr by 1/Lr1/L_r to make the container the unit cube. The scaled objects then have coordinate widths at most 11, as assumed in § 4.1, and for a candidate satisfying these bounds they can be packed together in the unit cube.

We then compute the enclosures FiF_i, round those with bi,ci≥1/nb_i,c_i \ge1/n to bcbc-parallelepipeds, and pack each of their O(log⁡2n)O(\log^2 n) types with Algorithm 1. For such a candidate, each type is packed into a box of volume Oε(nε)O_\varepsilon(n^\varepsilon) by Lemma 14. We handle the remaining objects separately, combine all boxes, and undo the scaling, returning the smallest-volume packing over all candidates. The four steps for a candidate are as follows.

  1. Rounded objects. For each KiK_i whose enclosure has bi,ci≥1/nb_i,c_i \ge1/n, we compute the bcbc-parallelepiped PiP_i and pack each type separately with Algorithm 1.

  1. Flat objects. We pack each KiK_i whose enclosure has ci<1/nc_i < 1/n into its own bounding box.

  1. Thin objects. We fan-pack the remaining enclosures, which have bi<1/n≤cib_i < 1/n \le c_i, as in Algorithm 1, with one object per block.

  1. Combining. We combine the boxes from these steps into a single box using Lemma 15.

Algorithm 2 summarizes the algorithm.

Algorithm 2 Packing convex polyhedra

1: Let Wr=max⁡iwr(Ki)W_r = \max_i w_r(K_i) for r∈{x,y,z}r \in\{x,y,z\}.

2: for each candidate container with side lengths Lr∈{2jWr:0≤j≤⌈log⁡2n⌉}L_r \in\{2^j W_r : 0 \le j \le\lceil\log_2 n\rceil\} do

3: Scale coordinate rr by 1/Lr1/L_r and compute FiF_i.

4: Compute PiP_i for bi,ci≥1/nb_i,c_i \ge1/n; pack each type with Algorithm 1. ▷ Step 1

5: Pack KiK_i with ci<1/nc_i < 1/n in their bounding boxes. ▷ Step 2

6: Fan-pack FiF_i with bi<1/n≤cib_i < 1/n \le c_i, one per block. ▷ Step 3

7: Combine the boxes using Lemma 15. ▷ Step 4

8: Undo the scaling.

9: end for

10: return the packing of smallest volume.

The combining step uses the following lemma.

Lemma 15. Let 0<s≤10 < s \le1 and h>0h > 0. Suppose that objects whose xx- and yy-widths are at most 1−s1-s and whose zz-widths are at most hh are packed by translations into boxes of total volume VV. In polynomial time, they can be repacked by translations into the box [0,1]×[0,1]×[0,64V/s2+16h][0,1] \times[0,1] \times[0,64V/s^2 + 16h].

Proof. We subdivide each box into cells of length ss in the xx- and yy-directions and hh in the zz-direction, and assign each object to the cell containing the corner of its bounding box with the smallest coordinates. We extend each cell by 1−s1-s in the xx- and yy-directions and by hh in the zz-direction, and take its intersection with the original box. Each resulting box contains all objects assigned to its cell and has a base fitting into [0,1]2[0,1]^2 and height at most 2h2h; see Figure 8.

Cutting into cells and packing the extended cells into a box

Figure 8. The repacking of Lemma 15, shown in the plane with the strip extending to the right. (a) Each s×hs \times h cell is extended by 1−s1-s across the strip and hh along it, then intersected with its box (outlined for one cell). (b) The extended cells (dotted), of dimensions at most 1×2h1 \times2h, are packed with their assigned objects into a box of width 1.

Fix a point p=(x,y,z)p=(x,y,z) in an original box. An extended cell containing pp must have its lower corner in [x−1,x]×[y−1,y]×[z−2h,z][x-1,x]\times[y-1,y]\times[z-2h,z], since its xx- and yy-widths are at most 11 and its zz-width at most 2h2h. The lower corners lie on a grid with spacings s,s,hs,s,h, giving at most 1/s+1≤2/s1/s+1\le2/s choices for each of the first two coordinates and at most 3≤43\le4 for the third. Thus pp lies in at most 16/s216/s^2 extended cells. Summing the cell volumes counts each point once for every cell containing it, so applying this bound in each original box gives total volume at most 16V/s216V/s^2.

To pack the extended cells, we use the classical strip packing result of Li and Cheng [33], as stated by Kar, Khan, and Rau [29]: axis-parallel boxes with bases fitting into [0,1]2[0,1]^2, heights at most h′h', and total volume WW can be packed by translations in polynomial time into [0,1]2×[0,4W+8h′][0,1]^2\times[0,4W+8h']. Packing each extended cell together with its assigned objects therefore gives height at most

4⋅16Vs2+8⋅2h=64Vs2+16h.4\cdot\frac{16V}{s^2}+8\cdot2h=\frac{64V}{s^2}+16h.

Proof of Theorem 1

Proof of Theorem 1. Every packed object contains the corresponding input polyhedron and all placements are translations, so Algorithm 2 returns a translational packing. To bound its volume, it suffices to consider a candidate satisfying Lr∗≤Lr<2Lr∗L_r^*\le L_r<2L_r^* in every coordinate. After scaling, the optimal packing fits inside the unit cube, and undoing the scaling multiplies volumes by LxLyLz<8OPT⁡volL_xL_yL_z<8\operatorname{OPT}_{\mathrm{vol}}. We now bound the volume of the boxes produced in Steps 1–3 for the scaled objects.

In Step 1, Lemma 14 shows that each of the O(log⁡2n)O(\log^2 n) types is packed into a box of volume Oε(n2ε)O_\varepsilon(n^{2\varepsilon}). In Step 2, each object fits into a box of dimensions 1×1×1n1\times1\times\frac{1}{n}, and these at most nn boxes can be stacked into the unit cube.

In Step 3, the yzyz-shadow of FiF_i is a parallelogram with edges (bi,0)(b_i,0) and (qi,ci)(q_i,c_i), where bi<1/nb_i<1/n. As in Algorithm 1, we order the enclosures by increasing slope qi/ciq_i/c_i and translate them so that the bottom edges of their shadows lie in the plane z=0z=0 and start at yy-coordinates 0,1/n,2/n,…0,1/n,2/n,\ldots. Since the slopes increase with these yy-coordinates, the shadows have disjoint interiors, so the enclosures do as well. All edge coordinates of the FiF_i are at most 77 in absolute value, so the enclosures fit into a box with xx-extent at most 2121, yy-extent at most n⋅1n+14=15n\cdot\frac{1}{n}+14=15, and zz-extent at most 77, which has volume O(1)O(1).

The boxes of Steps 1–3 therefore have total volume Oε(nεlog⁡2n)=Oε(n2ε)O_\varepsilon(n^{\varepsilon}\log^2 n)=O_\varepsilon(n^{2\varepsilon}). Since all packed objects have coordinate widths O(1)O(1), we scale by a constant to make these widths at most 1/21/2 and apply Lemma 15 with s=h=1/2s=h=1/2 in Step 4. This gives a box with base [0,1]2[0,1]^2 and height Oε(n2ε)O_\varepsilon(n^{2\varepsilon}), so undoing this constant scaling gives one box of volume Oε(n2ε)O_\varepsilon(n^{2\varepsilon}). Undoing the original coordinate scaling then multiplies this volume by less than 8OPT⁡vol8\operatorname{OPT}_{\mathrm{vol}}, so the returned packing has volume Oε(n2ε)⋅OPT⁡volO_\varepsilon(n^{2\varepsilon})\cdot\operatorname{OPT}_{\mathrm{vol}}, and replacing ε\varepsilon by ε/2\varepsilon/2 gives the claimed bound. Finally, there are O(log⁡3n)O(\log^3 n) candidates, each step for a candidate takes polynomial time, and no step depends on ε\varepsilon, so the same polynomial-time algorithm achieves the bound for every ε>0\varepsilon>0.

We conclude with a remark on the running time. The enclosures FiF_i are computed only once, since scaling the coordinates maps them to enclosures of the scaled objects. For each of the O(log⁡3(n))O(\log^3(n)) candidates, all remaining steps take O(nlog⁡n)O(n\log n) time, apart from the algorithm of Li and Cheng in Lemma 15, which is applied to at most nn boxes.

Bin packing and strip packing

We now prove Theorem 3. In translational bin packing, the objects must be packed by translations into as few unit cubes as possible. In translational strip packing, they must be packed into the strip [0,1]2×[0,∞)[0,1]^2 \times[0,\infty), minimizing the height of the packing.

Proof of Theorem 3. Let OPTbin\mathrm{OPT}_{\mathrm{bin}} be the minimum number of unit cubes and OPTstrip\mathrm{OPT}_{\mathrm{strip}} the minimum height. Placing the unit cubes of an optimal bin packing next to each other gives a packing into a box of volume OPTbin\mathrm{OPT}_{\mathrm{bin}}, and an optimal strip packing is itself a packing into a box of volume OPTstrip\mathrm{OPT}_{\mathrm{strip}}. Hence OPTvol≤OPTbin\mathrm{OPT}_{\mathrm{vol}} \le\mathrm{OPT}_{\mathrm{bin}} and OPTvol≤OPTstrip\mathrm{OPT}_{\mathrm{vol}} \le\mathrm{OPT}_{\mathrm{strip}}, and the α\alpha-approximation algorithm gives a packing into a box of volume V≤αOPTvolV \le\alpha\mathrm{OPT}_{\mathrm{vol}}.

We first consider strip packing. Let wrw_r be the largest rr-width of an object, so that wx,wy≤1−δw_x,w_y \le1-\delta. Lemma 15, applied to this box with s=δs=\delta and h=wzh=w_z, gives a packing into the strip of height at most 64V/δ2+16wz64V/\delta^2+16w_z. Every object fits into an optimal strip packing, so wz≤OPTstripw_z \le\mathrm{OPT}_{\mathrm{strip}}, and the height is at most 64αOPTstrip/δ2+16OPTstrip≤80δ−2α⋅OPTstrip64\alpha\mathrm{OPT}_{\mathrm{strip}}/\delta^2+16\mathrm{OPT}_{\mathrm{strip}} \le80\delta^{-2}\alpha\cdot\mathrm{OPT}_{\mathrm{strip}}.

For bin packing, we cut this strip packing, of height HH, into slabs of length δ\delta in the zz-coordinate and assign each object to the slab containing its lowest point. Since now also wz≤1−δw_z \le1-\delta, each object lies in its slab extended by 1−δ1-\delta, which is a box with base [0,1]2[0,1]^2 and height 11. We put each extended slab into its own unit cube. Stacking the unit cubes of an optimal bin packing gives a strip packing, so OPTstrip≤OPTbin\mathrm{OPT}_{\mathrm{strip}} \le\mathrm{OPT}_{\mathrm{bin}}. Since OPTbin≥1\mathrm{OPT}_{\mathrm{bin}} \ge1, this uses at most H/δ+1≤81δ−3α⋅OPTbinH/\delta+1 \le81\delta^{-3}\alpha\cdot\mathrm{OPT}_{\mathrm{bin}} unit cubes.

Concluding remarks

Although our packing algorithm is simple, its analysis relies on recent Kakeya estimates, and it remains open whether the same approximation guarantee can be proved using more elementary arguments. Using higher-dimensional Kakeya estimates for packing is a natural research direction, but arranging the higher-dimensional shadows poses a major obstacle, as it would require new ideas beyond the fan packing we use in two dimensions.

AI Methodology

We initially designed the algorithm with a completely different analysis in mind, which did not work out. We then asked ChatGPT 5.5 to repair this analysis. It did not succeed, but its reasoning traces showed that it was looking at the paper of Wang and Zahl [42], which made us aware of the connection to the Kakeya problem. Building on this, we developed the proof presented here. We also used GPT Astra 6 and Claude Opus 5.5 for literature search, for creating the TikZ figures, for assistance with language formulations, and for working out details based on the authors’ insights and general proof strategies. They also found the exact connection between the Kakeya maximal estimate in [38] and the tube-union bound needed for our analysis.

The tube-union estimate

Theorem 16 (Wang–Zahl [42, Theorem 1.2]). For all ε>0\varepsilon> 0, there exists K>1K > 1 so that the following holds for all δ>0\delta> 0 sufficiently small. Let T\mathcal{T} be a set of δ\delta-tubes contained in the unit ball in R3\mathbb{R}^{3}, and suppose that every rectangular prism of dimensions a×b×2a \times b \times2 contains at most 100abδ−2100ab\delta^{-2} tubes from T\mathcal{T} (this is true, for example, if the tubes in T\mathcal{T} point in δ\delta-separated directions). For each T∈TT \in\mathcal{T}, let Y(T)⊂TY(T) \subset T be a measurable set with ∣Y(T)∣≥λ∣T∣\lvert Y(T)\rvert\ge\lambda\lvert T\rvert. Then

∣⋃T∈TY(T)∣≥δελK∑T∈T∣T∣\left\lvert\bigcup_{T\in\mathcal{T}}Y(T)\right\rvert\ge\delta^{\varepsilon}\lambda^{K}\sum_{T\in\mathcal{T}}\lvert T\rvert

Taking Y(T)=TY(T)=T and λ=1\lambda=1 gives a bound on the union of the tubes in which the exponent KK plays no role. We then remove the restrictions on the tube locations and on δ\delta.

Proof of Theorem 4. Fix ε>0\varepsilon> 0 and choose 0<δε≤1100 < \delta_{\varepsilon} \le\frac{1}{10} so that Theorem 16 holds for all 0<δ<δε0 < \delta< \delta_{\varepsilon}. The tubes in T={Tδ(vi,xi):1≤i≤m}\mathcal{T}=\{T_{\delta}(v_i,x_i):1\le i\le m\} point in δ\delta-separated directions, since the unoriented angle between viv_i and vjv_j is at least δ\delta for i≠ji\ne j.

For δ<δε\delta< \delta_{\varepsilon}, we apply Theorem 16 locally to remove the unit-ball restriction. We partition the space into cubes of side 1/41/4 and let TQ\mathcal{T}_Q consist of the tubes whose segment midpoints lie in a cube QQ. Every point of such a tube is within distance 38+12+δ<1\frac{\sqrt{3}}{8}+\frac{1}{2}+\delta< 1 of the centre of QQ, so all tubes in TQ\mathcal{T}_Q lie in the unit ball centred there. The theorem therefore applies to each TQ\mathcal{T}_Q with Y(T)=TY(T)=T and λ=1\lambda=1.

Each point xx lies in at most 939^3 of these unit balls, since their centres must lie in x+[−1,1]3x+[-1,1]^3, which contains at most 939^3 points of the grid of spacing 1/41/4. Consequently,

vol⁡(⋃T∈TT)≥193∑Qvol⁡(⋃T∈TQT)≥δε93∑Q∑T∈TQvol⁡(T)=δε93∑T∈Tvol⁡(T).\begin{aligned} \operatorname{vol}\left(\bigcup_{T\in\mathcal{T}}T\right)\ge\frac{1}{9^3}\sum_Q\operatorname{vol}\left(\bigcup_{T\in\mathcal{T}_Q}T\right) \\ &\ge\frac{\delta^{\varepsilon}}{9^3}\sum_Q\sum_{T\in\mathcal{T}_Q}\operatorname{vol}(T)=\frac{\delta^{\varepsilon}}{9^3}\sum_{T\in\mathcal{T}}\operatorname{vol}(T). \end{aligned}

For δ≥δε\delta\ge\delta_{\varepsilon}, we bound the number of tubes by placing a cap of angular radius δε/2\delta_{\varepsilon}/2 around each viv_i on S2S^2. The caps have disjoint interiors, since the angles between the viv_i are at least δε\delta_{\varepsilon}, and each has area 4πsin⁡2(δε/4)≥δε2/π4\pi\sin^2(\delta_{\varepsilon}/4)\ge\delta_{\varepsilon}^2/\pi, using sin⁡x≥2x/π\sin x\ge2x/\pi for 0≤x≤π/20\le x\le\pi/2. Comparing their total area with the sphere’s area 4π4\pi gives at most N=4πδε−2N = 4\pi\delta_{\varepsilon}^{-2} tubes. Since their union contains the largest tube and δε≤1\delta^{\varepsilon} \le1, we obtain

vol⁡(⋃T∈TT)≥1N∑T∈Tvol⁡(T)≥δεN∑T∈Tvol⁡(T).\operatorname{vol}\left(\bigcup_{T\in\mathcal{T}}T\right) \ge\frac{1}{N}\sum_{T\in\mathcal{T}}\operatorname{vol}(T) \ge\frac{\delta^{\varepsilon}}{N}\sum_{T\in\mathcal{T}}\operatorname{vol}(T).

Taking Cε=max⁡{93,N}=O(δε−2)C_{\varepsilon}=\max\{9^3,N\}=O(\delta_{\varepsilon}^{-2}) proves Theorem 4. Thus CεC_{\varepsilon} depends on ε\varepsilon only through δε\delta_{\varepsilon}.

Polylogarithmic bounds

The factor nεn^{\varepsilon} in Theorem 1 arises solely from the δε\delta^{\varepsilon} loss in Theorem 4. To prove Theorem 2, we replace this estimate with the tube bounds of OpenAI [38, 37]. The preprint claims a loss of log⁡4(1/δ)\log^4(1/\delta) [38 Corollary 9.1], whereas the formalization verifies a bound with a loss of log⁡66(1/δ)\log^{66}(1/\delta). We show that these bounds yield approximation ratios O(log⁡7n)O(\log^7 n) and O(log⁡69n)O(\log^{69} n), respectively.

The tube estimates

Theorem 17 ([37 tube-union-logarithmic]). *There is a constant c0>0c_0>0 such that, for all 0<δ≤1/e0<\delta\le1/e, all v1,…,vm∈S2v_1,\ldots,v_m\in S^2 with ∥vi−vj∥≥δ\lVert v_i-v_j\rVert\ge\delta for i≠ji\ne j, and all x1,…,xm∈R3x_1,\ldots,x_m\in\mathbb{R}^3,

vol⁡(⋃i=1mTδ(vi,xi))≥c0mδ2(1+log⁡(1/δ))66.\operatorname{vol}\left(\bigcup_{i=1}^{m}T_{\delta}(v_i,x_i)\right)\ge\frac{c_0m\delta^2}{(1+\log(1/\delta))^{66}}.

The formalization states this bound in Rn\mathbb{R}^n, with mδn−1m\delta^{n-1} in the numerator and exponent 2n(2n+5)2n(2n+5), which equals 66 for n=3n=3; this statement does not seem to appear in [38]. As we will show, it yields Theorem 4 with the factor δε/Cε\delta^{\varepsilon}/C_{\varepsilon} replaced by Clog⁡−66(1/δ)C\log^{-66}(1/\delta) for some absolute constant C>0C>0. Here we absorb the additive 1 in the logarithmic factor into CC, using δ≤1/e\delta\le1/e.

Theorem 17 requires the Euclidean distance between any two direction vectors to be at least the tube radius, whereas our angular separation guarantees only ∥vi−vj∥≥2sin⁡(δ/2)≥2δ/π\lVert v_i-v_j\rVert\ge2\sin(\delta/2)\ge2\delta/\pi. We therefore replace each Tδ(vi,xi)T_{\delta}(v_i,x_i) by T2δ/π(vi,xi)T_{2\delta/\pi}(v_i,x_i), reducing its radius to 2δ/π2\delta/\pi. The direction vectors are separated by at least this new radius, so these replacement tubes satisfy the hypothesis of Theorem 17. Each replacement tube lies inside its original tube, so a lower bound on the volume of their union also bounds the volume of the original union from below.

Since changing the radius by a constant factor only affects the constants, Theorem 17 gives the desired bound with factor Clog⁡−66(1/δ)C\log^{-66}(1/\delta).

The preprint [38] instead claims a Kakeya maximal estimate, formulated using the Kakeya maximal function Kδf:S2→[0,∞]K_{\delta}f:S^2\to[0,\infty], defined for a locally integrable function f:R3→Rf:\mathbb{R}^3\to\mathbb{R} by

Kδf(ω)=sup⁡x∈R31vol⁡(Tδ(ω,x))∫Tδ(ω,x)∣f∣.K_{\delta}f(\omega)=\sup_{x\in\mathbb{R}^3}\frac{1}{\operatorname{vol}(T_{\delta}(\omega,x))}\int_{T_{\delta}(\omega,x)}|f|.

Thus Kδf(ω)K_{\delta}f(\omega) is the supremum of the averages of ∣f∣|f| over tubes of length 1 and radius δ\delta in direction ω\omega. For example, if EE is a union of such tubes and f=1Ef=1_E, then Kδf(ω)=1K_{\delta}f(\omega)=1 whenever one of the tubes has direction ω\omega. For nearby directions, a tube still lies largely in EE, so KδfK_{\delta}f remains close to 1. We measure KδfK_{\delta}f and ff using the norms

∥Kδf∥L3(S2)=(∫S2(Kδf(ω))3 dω)1/3and∥f∥L3(R3)=(∫R3∣f(x)∣3 dx)1/3.\lVert K_{\delta}f\rVert_{L^3(S^2)}=\left(\int_{S^2}(K_{\delta}f(\omega))^3\,d\omega\right)^{1/3} \quad\text{and}\quad \lVert f\rVert_{L^3(\mathbb{R}^3)}=\left(\int_{\mathbb{R}^3}|f(x)|^3\,dx\right)^{1/3}.

We write L3(R3)L^3(\mathbb{R}^3) for the space of functions with finite L3L^3 norm. For an indicator function f=1Ef = 1_E, this norm is ∥f∥L3(R3)=vol⁡(E)1/3\lVert f\rVert_{L^3(\mathbb{R}^3)} = \operatorname{vol}(E)^{1/3}.

Theorem 18 [38 Corollary 9.1]. There is a constant CK≥1C_K \ge1 such that, for all 0<δ≤10 < \delta\le1 and all f∈L3(R3)f \in L^3(\mathbb{R}^3),

∥Kδf∥L3(S2)≤CKlog⁡4/3(2/δ)∥f∥L3(R3).\lVert K_\delta f\rVert_{L^3(S^2)} \le C_K \log^{4/3}(2/\delta) \lVert f\rVert_{L^3(\mathbb{R}^3)}.

The preprint states this estimate in Rn\mathbb{R}^n for every n≥2n \ge2, with the LnL^n norms and the power 4pc\frac{4}{p_c}, where pc=2nn−1p_c = \frac{2n}{n-1}; for n=3n = 3, this is the power 43\frac{4}{3} above.

Lemma 19. If Theorem 18 holds, then, for 0<δ≤1/e0 < \delta\le1/e, the logarithmic factor in Theorem 17 can be replaced by log⁡−4(1/δ)\log^{-4}(1/\delta).

Proof. Let 0<δ≤1/e0 < \delta\le1/e and let v1,…,vmv_1,\ldots,v_m and x1,…,xmx_1,\ldots,x_m be as in Theorem 17. Write E=⋃i=1mTδ(vi,xi)E = \bigcup_{i=1}^m T_\delta(v_i,x_i) and f=1Ef = 1_E, and for each ii define the cap of angular radius δ/3\delta/3 centred at viv_i by

Bi={ω∈S2:arccos⁡(ω⋅vi)≤δ3}.B_i = \left\{\omega\in S^2 : \arccos(\omega\cdot v_i) \le\frac{\delta}{3}\right\}.

These caps are disjoint. Indeed, suppose that ω\omega lies in both BiB_i and BjB_j. Angles between unit vectors satisfy the triangle inequality, so the angle between viv_i and vjv_j is

arccos⁡(vi⋅vj)≤arccos⁡(ω⋅vi)+arccos⁡(ω⋅vj)≤2δ3.\arccos(v_i\cdot v_j) \le\arccos(\omega\cdot v_i) + \arccos(\omega\cdot v_j) \le\frac{2\delta}{3}.

Since a chord of the unit circle is shorter than the corresponding arc, ∥vi−vj∥≤arccos⁡(vi⋅vj)≤2δ3<δ\lVert v_i-v_j\rVert\le\arccos(v_i\cdot v_j) \le\frac{2\delta}{3}<\delta, contradicting the assumption ∥vi−vj∥≥δ\lVert v_i-v_j\rVert\ge\delta.

A cap of angular radius α\alpha has area 2π(1−cos⁡α)=4πsin⁡2α22\pi(1-\cos\alpha)=4\pi\sin^2\frac{\alpha}{2}. Since sin⁡x≥2xπ\sin x\ge\frac{2x}{\pi} for 0≤x≤π20\le x\le\frac{\pi}{2}, each BiB_i has area at least

4πsin⁡2δ6≥4π(δ3π)2=4δ29π≥δ28.4\pi\sin^2\frac{\delta}{6}\ge4\pi\left(\frac{\delta}{3\pi}\right)^2=\frac{4\delta^2}{9\pi}\ge\frac{\delta^2}{8}.

We claim that Kδf(ω)≥18K_\delta f(\omega)\ge\frac18 for every ω∈Bi\omega\in B_i. Let S=xi+12Tδ(ω,0)S=x_i+\frac12T_\delta(\omega,0). Then S⊂Tδ(ω,xi)S\subset T_\delta(\omega,x_i) and vol⁡(S)=18vol⁡(Tδ(ω,xi))\operatorname{vol}(S)=\frac18\operatorname{vol}(T_\delta(\omega,x_i)). Moreover, S⊂Tδ(vi,xi)⊂ES\subset T_\delta(v_i,x_i)\subset E. Indeed, let xi+tω+ex_i+t\omega+e be a point of SS, with ∣t∣≤14\lvert t\rvert\le\frac14 and ∥e∥<δ2\lVert e\rVert<\frac{\delta}{2}. Since ∥ω−vi∥≤arccos⁡(ω⋅vi)≤δ3\lVert\omega-v_i\rVert\le\arccos(\omega\cdot v_i)\le\frac{\delta}{3}, its distance to the point xi+tvix_i+tv_i of the axis segment of Tδ(vi,xi)T_\delta(v_i,x_i) is at most

∣t∣∥ω−vi∥+∥e∥<14⋅δ3+δ2<δ.\lvert t\rvert\lVert\omega-v_i\rVert+\lVert e\rVert<\frac14\cdot\frac{\delta}{3}+\frac{\delta}{2}<\delta.

Hence EE covers at least 18\frac18 of the tube Tδ(ω,xi)T_\delta(\omega,x_i), which gives Kδf(ω)≥18K_\delta f(\omega)\ge\frac18.

We now bound ∥Kδf∥L3(S2)3\lVert K_\delta f\rVert_{L^3(S^2)}^3 from both sides:

mδ284≤∑i=1m∫Bi(Kδf(ω))3 dωsince Kδf≥18 on Bi and Bi has area at least δ28,≤∫S2(Kδf(ω))3 dωsince the caps Bi are disjoint,=∥Kδf∥L3(S2)3by the definition of the norm,≤CK3log⁡4(2/δ)∥f∥L3(R3)3by xref‘Theorem 18‘,=CK3log⁡4(2/δ)vol⁡(E)since f=1E.\begin{aligned} \frac{m\delta^2}{8^4} &\le\sum_{i=1}^m\int_{B_i}(K_\delta f(\omega))^3\,d\omega &&\text{since }K_\delta f\ge\frac18\text{ on }B_i\text{ and }B_i\text{ has area at least }\frac{\delta^2}{8},\\ &\le\int_{S^2}(K_\delta f(\omega))^3\,d\omega &&\text{since the caps }B_i\text{ are disjoint},\\ &= \lVert K_\delta f\rVert_{L^3(S^2)}^3 &&\text{by the definition of the norm},\\ &\le C_K^3\log^4(2/\delta)\lVert f\rVert_{L^3(\mathbb{R}^3)}^3 &&\text{by {xref}`Theorem 18`},\\ &= C_K^3\log^4(2/\delta)\operatorname{vol}(E) &&\text{since }f=1_E. \end{aligned}

Rearranging gives the claimed bound with c0=116⋅84CK3c_0=\frac{1}{16\cdot8^4C_K^3}.

Proof of Theorem 2

Proof of Theorem 2. We follow the proof of Theorem 1, but use Theorem 17 in place of Theorem 4. By the remark after Theorem 17, this replaces the factor δε/Cε\delta^{\varepsilon}/C_{\varepsilon} by Clog⁡−66(1/δ)C\log^{-66}(1/\delta). We trace this change through the three steps of the analysis.

First, Theorem 8 holds with CεnεC_{\varepsilon}n^{\varepsilon} replaced by O(log⁡66n)O(\log^{66} n). Indeed, the volume bound of § 3, with δ=bτ1000\delta= \frac{b\tau}{1000} and the new factor, shows that at most

O(log⁡66(1000/(bτ))bcτ)O\left(\frac{\log^{66}(1000/(b\tau))}{bc\tau}\right)

objects have ai<τ100a_i < \frac{\tau}{100}. If bτ≥n−2b\tau\ge n^{-2}, then log⁡1000bτ≤log⁡(1000n2)=O(log⁡n)\log\frac{1000}{b\tau} \le\log(1000n^2) = O(\log n), so this number is O(log⁡66nbcτ)O\left(\frac{\log^{66} n}{bc\tau}\right); if bτ<n−2b\tau< n^{-2}, then ∣P∣≤n<1bτ≤1bcτ|\mathcal{P}| \le n < \frac{1}{b\tau} \le\frac{1}{bc\tau} anyway. Together with the at most 100bcτ\frac{100}{bc\tau} objects with ai≥τ100a_i \ge\frac{\tau}{100}, this gives ∣P∣=O(log⁡66nbcτ)|\mathcal{P}| = O\left(\frac{\log^{66} n}{bc\tau}\right).

Second, with this bound, the computation in the proof of Lemma 9 gives

bc∑kMST⁡k≤1+O(log⁡66n)ln⁡(2n)=O(log⁡67n),bc\sum_k \operatorname{MST}_k \le1 + O(\log^{66} n)\ln(2n) = O(\log^{67} n),

so, by the proof of Lemma 14, each type is packed into a box of volume O(log⁡67n)O(\log^{67} n).

Finally, there are O(log⁡2n)O(\log^2 n) types, so the boxes of Steps 1–3 in the proof of Theorem 1 have total volume O(log⁡69n)O(\log^{69} n). The rest of that proof is unchanged, so the returned packing has volume O(log⁡69n)⋅OPTvolO(\log^{69} n)\cdot\mathrm{OPT}_{\mathrm{vol}}.

If Theorem 18 holds, then by Lemma 19 the same argument works with the exponent 6666 replaced by 44 throughout, which gives the approximation ratio O(log⁡7n)O(\log^7 n). □

References

  1. [1]Anders Aamand, Mikkel Abrahamsen, Simon Bartlmae, Arindam Khan, Linda Kleist, and Csaba D. Tóth. Online Geometric Packing through Online TSP Scheduling. In SODA. SIAM, 2027. To appear. Full version: arXiv:2607.22179.arxiv.org/abs/2607.22179
  2. [2]Anders Aamand, Mikkel Abrahamsen, Lorenzo Beretta, and Linda Kleist. Online Sorting and Translational Packing of Convex Polygons. In SODA, pages 1806–1833. SIAM, 2023. doi:10.1137/1.9781611977554.ch69.DOI
  3. [3]Sara Ali, António Galrão Ramos, Maria Antónia Carravilla, and José Fernando Oliveira. On-line three-dimensional packing problems: A review of off-line and on-line solution approaches. Comput. Ind. Eng., 168:108122, 2022. doi:10.1016/j.cie.2022.108122.DOI
  4. [4]Helmut Alt. Computational Aspects of Packing Problems. Bull. EATCS, 118, 2016.
  5. [5]Helmut Alt, Sergio Cabello, Otfried Cheong, Ji-won Park, and Nadja Seiferth. Packing d-dimensional balls into a d + 1-dimensional container. Comput. Geom., 132:102219, 2026. doi:10.1016/j.comgeo.2025.102219.DOI
  6. [6]Helmut Alt, Mark de Berg, and Christian Knauer. Approximating Minimum-Area Rectangular and Convex Containers for Packing Convex Polygons. J. Comput. Geom., 8(1):1–10, 2017. doi:10.20382/jocg.v8i1a1.DOI
  7. [7]Helmut Alt and Nadja Scharf. Approximating Smallest Containers for Packing Three-Dimensional Convex Objects. Int. J. Comput. Geom. Appl., 28(2):111–128, 2018. doi:10.1142/S0218195918600026.DOI
  8. [8]Luiz J. P. Araújo, Ender Özcan, Jason A. D. Atkin, and Martin Baumers. Analysis of irregular three-dimensional packing problems in additive manufacturing: a new taxonomy and dataset. Int. J. Prod. Res., 57(18):5920–5934, 2019. doi:10.1080/00207543.2018.1534016.
  9. [9]Luiz J. P. Araújo, Ajit Panesar, Ender Özcan, Jason Atkin, Martin Baumers, and Ian Ashcroft. An experimental analysis of deepest bottom-left-fill packing methods for additive manufacturing. Int. J. Prod. Res., 58(22):6917–6933, 2020. doi:10.1080/00207543.2019.1686187.
  10. [10]Nikhil Bansal, Xin Han, Kazuo Iwama, Maxim Sviridenko, and Guochuan Zhang. A Harmonic Algorithm for the 3D Strip Packing Problem. SIAM J. Comput., 42(2):579–592, 2013. doi:10.1137/070691607.DOI
  11. [11]Alberto Caprara. Packing d-Dimensional Bins in d Stages. Math. Oper. Res., 33(1):203–215, 2008. doi:10.1287/moor.1070.0289.DOI
  12. [12]Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan. Approximating the Minimum Spanning Tree Weight in Sublinear Time. SIAM J. Comput., 34(6):1370–1379, 2005. doi:10.1137/S0097539702403244.DOI
  13. [13]Henrik I. Christensen, Arindam Khan, Sebastian Pokutta, and Prasad Tetali. Approximation and online algorithms for multidimensional bin packing: A survey. Comput. Sci. Rev., 24:63–79, 2017. doi:10.1016/j.cosrev.2016.12.001.DOI
  14. [14]Edward G. Coffman Jr., János Csirik, Gábor Galambos, Silvano Martello, and Daniele Vigo. Bin Packing Approximation Algorithms: Survey and Classification. In Handbook of Combinatorial Optimization, pages 455–531. Springer, 2013. doi:10.1007/978-1-4419-7997-1_35.DOI
  15. [15]János Csirik and André van Vliet. An on-line algorithm for multidimensional bin packing. Oper. Res. Lett., 13(3):149–158, 1993. doi:10.1016/0167-6377(93)90004-Z.DOI
  16. [16]Mark de Berg and Christian Knauer. Corrigendum to: Approximating minimum-area rectangular and convex containers for packing convex polygons. J. Comput. Geom., 11(1):653–655, 2020. doi:10.20382/jocg.v11i1a26.DOI
  17. [17]Florian Diedrich, Rolf Harren, Klaus Jansen, Ralf Thöle, and Henning Thomas. Approximation Algorithms for 3D Orthogonal Knapsack. J. Comput. Sci. Technol., 23(5):749–762, 2008. doi:10.1007/s11390-008-9170-7.DOI
  18. [18]Jens Egeblad, Benny K. Nielsen, and Marcus Brazil. Translational packing of arbitrary polytopes. Comput. Geom., 42(4):269–288, 2009. doi:10.1016/j.comgeo.2008.06.003.
  19. [19]Jens Egeblad, Benny K. Nielsen, and Allan Odgaard. Fast neighborhood search for two- and three-dimensional nesting problems. Eur. J. Oper. Res., 183(3):1249–1266, 2007. doi:10.1016/j.ejor.2005.11.063.
  20. [20]Leah Epstein and Rob van Stee. Optimal Online Algorithms for Multidimensional Packing Problems. SIAM J. Comput., 35(2):431–448, 2005. doi:10.1137/S0097539705446895.DOI
  21. [21]Paul C. Gilmore and Ralph E. Gomory. Multistage Cutting Stock Problems of Two and More Dimensions. Oper. Res., 13(1):94–120, 1965. doi:10.1287/opre.13.1.94.DOI
  22. [22]Valeriya Griffiths, James P. Scanlan, Murat H. Eres, Antonio Martinez-Sykora, and Phani Chinchapatnam. Cost-driven build orientation and bin packing of parts in Selective Laser Melting (SLM). Eur. J. Oper. Res., 273(1):334–352, 2019. doi:10.1016/j.ejor.2018.07.053.DOI
  23. [23]Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer, 1988. doi:10.1007/978-3-642-97881-4.DOI
  24. [24]Rolf Harren. Approximation algorithms for orthogonal packing problems for hypercubes. Theor. Comput. Sci., 410(44):4504–4532, 2009. doi:10.1016/j.tcs.2009.07.030.DOI
  25. [25]Frank K. Hwang. An O(n log n) Algorithm for Rectilinear Minimal Spanning Trees. J. ACM, 26(2):177–182, 1979. doi:10.1145/322123.322124.DOI
  26. [26]Klaus Jansen and Lars Prädel. A New Asymptotic Approximation Algorithm for 3-Dimensional Strip Packing. In SOFSEM, volume 8327 of Lecture Notes in Computer Science, pages 327–338. Springer, 2014. doi:10.1007/978-3-319-04298-5_29.DOI
  27. [27]Klaus Jansen and Roberto Solis-Oba. An asymptotic approximation algorithm for 3D-strip packing. In SODA, pages 143–152. ACM Press, 2006. doi:10.1145/1109557.1109575.DOI
  28. [28]Fritz John. Extremum problems with inequalities as subsidiary conditions. In Studies and Essays Presented to R. Courant on his 60th Birthday, pages 187–204. Interscience, 1948.
  29. [29]Debajyoti Kar, Arindam Khan, and Malin Rau. Improved Approximation Algorithms for Three-Dimensional Bin Packing. In ICALP, volume 334 of LIPIcs, pages 104:1–104:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.ICALP.2025.104.DOI
  30. [30]Adam Kurpisz and Silvan Suter. Improved Approximations for Translational Packing of Convex Polygons. In ESA, volume 274 of LIPIcs, pages 76:1–76:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.ESA.2023.76.arxiv.org/abs/2308.08523
  31. [31]Carlos Lamas-Fernandez, Julia A. Bennell, and Antonio Martinez-Sykora. Voxel-Based Solution Approaches to the Three-Dimensional Irregular Packing Problem. Oper. Res., 71(4):1298–1317, 2023. doi:10.1287/opre.2022.2260.
  32. [32]Aline A. S. Leao, Franklina M. B. Toledo, José Fernando Oliveira, Maria Antónia Carravilla, and Ramón Alvarez-Valdés. Irregular packing problems: A review of mathematical models. Eur. J. Oper. Res., 282(3):803–822, 2020. doi:10.1016/j.ejor.2019.04.045.DOI
  33. [33]Keqin Li and Kam-Hoi Cheng. On Three-Dimensional Packing. SIAM J. Comput., 19(5):847–867, 1990. doi:10.1137/0219059.DOI
  34. [34]Aram Meir and Leo Moser. On packing of squares and cubes. J. Comb. Theory, 5(2):126–134, 1968. doi:10.1016/S0021-9800(68)80047-X.DOI
  35. [35]Flávio Keidi Miyazawa and Yoshiko Wakabayashi. An algorithm for the three-dimensional packing problem with asymptotic performance analysis. Algorithmica, 18(1):122–144, 1997. doi:10.1007/BF02523692.DOI
  36. [36]Yosep Oh, Paul Witherell, Yan Lu, and Timothy Sprock. Nesting and scheduling problems for additive manufacturing: A taxonomy and review. Additive Manufacturing, 36:101492, 2020. doi:10.1016/j.addma.2020.101492.DOI
  37. [37]OpenAI. Lean formalization of local smoothing for the Euclidean wave equation. OpenAI Math Release, theorem tube_union_logarithmic in lean/OAI/MeasureTheory/Kakeya/Logarithmic.lean, 2026. URL: https://github.com/openai/math/blob/main/lean/OAI/MeasureTheory/Kakeya/Logarithmic.lean.
  38. [38]OpenAI. Local smoothing for the Euclidean wave equation. OpenAI Math Release preprint, October 25, 2026, 2026. URL: https://github.com/openai/math/blob/main/preprints/Local-smoothing-for-the-Euclidean-wave-equation-October-25-2026/paper.pdf.hub.valency.io/works/W_r5p3dy7d
  39. [39]Nadja Seiferth. Algorithmic Aspects of Packing Problems. PhD thesis, FU Berlin, Germany, 2022. doi:10.17169/refubium-35132.DOI
  40. [40]Eklavya Sharma. Harmonic Algorithms for Packing d-Dimensional Cuboids into Bins. In FSTTCS, volume 213 of LIPIcs, pages 32:1–32:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.FSTTCS.2021.32.DOI

Paper details

vlnc:W_jsj7undc
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents