WorksComputer Science
Polylogarithmic Approximation for Packing Convex Polyhedra
Abstract
We study translational packing of convex polyhedra in three dimensions. Given convex polyhedra in , 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 -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 , we obtain the same approximation guarantees for translational packing of convex polyhedra whose coordinate widths are at most a 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 convex polyhedra in , 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 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 -approximation algorithm for translational packing of convex polyhedra in into a minimum-volume axis-parallel box.
More precisely, for every , the approximation ratio is at most for some constant , while the algorithm and its running time are independent of . The constant depends on unspecified constants in Wang and Zahl’s Kakeya estimate [42], so we do not make the 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 . If the Kakeya maximal estimate claimed by OpenAI [38 Corollary 9.1] holds, the ratio improves to .
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 of minimum height . 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 into a minimum-volume axis-parallel box admits a polynomial-time -approximation. Then, for every , translational bin packing and strip packing of convex polyhedra with coordinate widths at most admit polynomial-time - and -approximation algorithms, respectively.
We prove Theorem 3 in § 5. By Theorem 1, we can take , and by Theorem 2, even .
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
where is the minimum area of an axis-parallel rectangle containing a translational packing, and 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 . 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 , with constants depending on .
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.
Table 1. Approximation guarantees for minimum-area (2D) and minimum-volume (3D) axis-parallel containers. Rigid motions allow rotations. For congruent planar shapes, 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 unit-radius planar disks in , with arbitrary normal vectors: their total three-dimensional volume is zero and each coordinate width is at most , so the bound is at most . Yet there are choices of normal vectors for which every translational packing requires volume [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 , where 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 , , and , the tube is the open -neighbourhood of the unit segment . For , it has volume . For vectors , we define the unoriented angle between them to be the minimum of the angle between and and the angle between and .
Theorem 4. *For every , there exists a constant such that the following holds for all . Let be such that for distinct , the unoriented angle between and
is at least , and let . Then
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 , 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 types, with only a constant-factor enlargement. Within each type, the shadows (projections) onto the -plane all have the same area , 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 -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 for the tree weight of shadow group , the resulting packing has volume , where 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 , giving only possible values for the scale. Some value, say , accounts for of the total weight, so there are edges of that length. These edges of the MSTs allow us to select representative objects such that any two from the same shadow group have distance at least . Indeed, by the MST property, after removing the edges of length at least , we end up with connected components such that the distance between any two pieces in different connected components is at least , 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 -direction to thickness . Each resulting object has volume , so their total volume is . 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 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 ,
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 -axis, one edge parallel to the -plane, and one edge with a positive -component (see Figure 1).

Figure 1. A -parallelepiped with , translated so that one vertex is at the origin (a), and its projections onto the -plane (b) and the -plane (c). The edges are , , and . Objects with the same share the -projection.
We fix the -component of the second edge, and the -component of the third edge. The components , , and of the second and third edges describe how the objects slant. More precisely, for fixed , a -parallelepiped is a translate of
where , and are the four free parameters. Here is the length of the first edge, and are the -components of the second and third edges, while specifies the third edge’s -component in multiples of . Objects sharing form a type, and object has volume . We consider a single type with objects . We assume that each object fits individually in the unit cube, or equivalently that
The projection onto the -plane maps the three edges to , , and , so the shadow of is the parallelogram spanned by and ; see Figure 1(c). Within a type, this shadow depends only on , not on and . Objects with form shadow class .
One way to pack objects of the same shadow class is to translate them only along the -axis, so that their shadows coincide. The distance required between two such objects is determined by their shears and . For two objects and , let
The following lemma shows that their centres then need to be exactly apart.
Lemma 5. Let and be objects of the same shadow class. Then and have disjoint interiors if and only if .
Proof. The common shadow of the shadow class consists of the points with . The point of lies above exactly when and . Hence, above this point, and occupy the -intervals and . These intervals overlap in an interval of positive length exactly when the distance between their midpoints is less than . The distance between their midpoints is , where
As and range over , the values of form the interval , with the endpoints attained at corners.
If , then either or , so 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 . The value of the interval closest to 0 has absolute value , so for some with . Above the corresponding interior point of the shadow, the two -intervals overlap in an interval of positive length, whose interior points are interior points of both objects. □
Thus, placing objects with similar -values consecutively saves space. We write for the minimum spanning tree weight of shadow class under .
The algorithm
The algorithm places the objects in three steps, illustrated in Figure 2 and summarized in Algorithm 1.
Figure 2. Packing -parallelepipeds of varying thickness , with colors indicating shadow classes. (a) Each class is lined up along the -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 . We translate object by , where the first object gets the offset , and every later object gets the offset , where 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 form a block, and we translate each block by , so that all offsets lie in . Since , every object lies within -distance of its offset, so every block lies in the slab , and no object is cut. Without this step, a single long shadow class could determine the -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 in order of increasing shadow class , breaking ties arbitrarily, and translate the -th block, of class , by , 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 increases and never cross.
The next lemma ensures that objects in different blocks do not overlap.
Lemma 6. Let and be objects with , and let be integers. Then, for all , the objects and have disjoint interiors.
Algorithm 1 Packing -parallelepipeds
for each nonempty shadow class do
Order the class as by the MST-based 2-approximation.
Set and for .
end for
Number the blocks, i.e. the distinct pairs , as in order of increasing .
Let be the number of the block containing .
Translate each by .
return these translations and the axis-parallel bounding box.
Proof. At height , where , the two objects have -coordinates in and , respectively. The second interval starts where the first ends or later, because the difference of their midpoints is .
Lemma 7. In time, Algorithm 1 returns a translational packing of in an axis-parallel box of volume
Proof. We first show that no two objects overlap. Consider two objects , labelled so that . If they lie in the same block, their translations differ only in the -coordinate, by , and we may assume that comes before in their class. The distance is the -distance between the points , so the triangle inequality gives , and Lemma 5 applies. If they lie in different blocks, then and hence , so Lemma 6 applies.
Next, we bound the volume. The offsets of class lie in , where is the sum of the in the class, so the class produces at most blocks. Since , at most classes are nonempty, so the total number of blocks satisfies
The final packing lies in , since the -th block has -coordinates within of and . Multiplying the side lengths proves the bound.
Finally, we bound the running time. The distance is the -distance between the points , so a minimum spanning tree of a class with objects can be computed in time [25]. Finally, sorting the at most blocks by shadow class takes time.
Bounding the spanning-tree cost
Since and for families that fit in the unit cube, it remains to bound . For a shadow class , let be the complete graph on its objects with edge weights . For , define
where is the weight of edge , and let be its number of connected components. Since each object fits in the unit cube, , so all edge weights are at most 2. We have the identity
Indeed, a minimum spanning tree has exactly edges of weight greater than : deleting these edges leaves a forest whose trees exactly correspond to the components of . Each tree lies in one component, since its edges belong to . Conversely, if there are two or more trees in the same connected component, then there is also an edge of joining two such trees. Hence, the path from to in the minimum spanning tree would contain a deleted edge, which is heavier than . Exchanging the two edges would give a lighter spanning tree. An edge of weight of the minimum spanning tree is therefore counted for and contributes exactly 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
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 , the total number of components at scale , for every . We bound this sum for all shadow classes together, since bounding each class separately would lose a factor of the number of classes.
Fix and choose one representative from each component of every . These objects still fit in the unit cube, and two representatives of the same shadow class satisfy , since otherwise an edge would join their components. The following theorem, the geometric lower bound at the core of our analysis, therefore bounds ; we prove it in § 3.
Theorem 8 (Lower Bound). For every , there exists a constant such that the following holds. Let be a family of at most -parallelepipeds that can be packed by translations into the unit cube. If, for some , we have for every pair of distinct objects with , then
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:
they are -parallelepipeds of a single type;
they form a subfamily of the input, so they can be packed by translations into the unit cube;
any two representatives with lie in different components of , so .
Hence, for every ,
It remains to integrate over from 0 to 2. Small scales are handled by the trivial bound of components, and larger scales by Theorem 8.
Lemma 9. If are -parallelepipeds that admit a translational packing into the unit cube, then, for every ,
Proof. Choosing one object from each component of the graphs gives a family satisfying Theorem 8, so . The MST identity (2), split at , now gives
Finally, we absorb the logarithm and rescale .
Together with Lemma 7, and since and , this shows that if admit a translational packing into the unit cube, then Algorithm 1 packs them into a box of volume . 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 of Theorem 1.
The lower bound
In this section, we prove Theorem 8 by a purely geometric argument.
We fix a family satisfying its assumptions, so that for any two distinct objects with , and fix a packing in . Throughout the rest of this section, denotes the placed object and its center. Its parameters satisfy
Object has volume , so volume counting shows that at most objects have . For objects with , however, volume counting is far too weak. We therefore thicken these objects in the -direction so that each has volume roughly , 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 objects have , so it suffices to bound the number of objects with , and we consider only these from now on; let be the family of these objects. We cut the real line into intervals of length and label them from left to right.

Figure 3. Partitioning the offsets into slope groups. Each point represents one object; the highlighted intervals illustrate retaining label 3.
We then retain only the objects whose -values lie in intervals of the label that contains the most -values. Objects whose -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 , up to a factor of 10. Moreover, two intervals with the same label are always separated by a gap of at least .
For every retained object, define the auxiliary body
Thus has the same center as , a first edge of length , and one quarter of its second edge. In each plane parallel to the -plane, this is precisely the shortening and thickening shown in Figure 4. Its volume is .

Figure 4. Intersections of the objects with a plane parallel to the -plane. (a) Original objects and their thickened middle portions . (b) If and share a point , the center lines of and (dashed) are less than apart at , so they cross at a point less than from in , 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 lies in .
Proof. Suppose, for a contradiction, that and from different retained groups share an interior point . In the plane through parallel to the -plane, each auxiliary body is a thickened middle quarter of the corresponding parallelogram section of or ; see Figure 4(a). The center lines of the original sections have slopes and . Since lies in both thickened sections, the lines are less than apart in the -direction at ’s -coordinate. Their slopes differ by , so they intersect at a point within a -distance of from ; see Figure 4(b).
By (3), shortening retains the middle quarter of each original section in the -direction, so is at least from either end in that direction. Since , the intersection point lies inside both original sections and is therefore an interior point of both and . 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 on either side in the -direction, proving the stated containment.
Finding Tubes For a retained interval with midpoint , define
which has . Applying this map to (3), gives
Let denote the third edge vector in (4), with unit direction , and set . The following lemma shows that each contains a tube of radius in direction , with the tube directions pairwise -separated within each retained slope group.
Lemma 11. Within each retained slope group, every contains the tube , and the unoriented angle between and is at least for each .
Proof. The first two edge vectors in (4) span a parallelogram in the -plane of -width and -height . Since , the shear satisfies
This bound on the shear implies that the parallelogram contains the disk centered at the origin with radius ; see Figure 5. Moreover, follows from , , , and . After translating so that , (4) gives

Figure 5. The disk in has radius and yields a tube along the object. Arrows show the generating edges, labeled with their -components; the drawings are schematic and not to scale.
To prove the tube containment, it suffices to show that contains , the -neighbourhood of the segment . Any point in this set can be written as , where and . Writing for the -coordinate of , we have
Because has -coordinate , the vector lies in the -plane and satisfies
Thus , while the coefficient of has absolute value at most . The point therefore lies in , proving the claimed containment.
For the angular separation, take distinct objects in the same group. If , the second coordinates of and differ by at least . If , the separation assumption and give , so their first coordinates differ by more than . In either case,
Let be the unoriented angle between and , and consider the triangle with vertices , , and . Its area is . The line through and lies in the plane , so its distance from the origin is at least and the area is at least . Comparing these bounds gives
The volume bound
Fix a retained interval containing objects. By Lemma 11, the tubes with have pairwise -separated directions, so Theorem 4 applies with . Using , , and , we obtain
By Lemma 10, the unions for distinct retained intervals have disjoint interiors and lie in a common box of volume . Summing the preceding bound over the retained intervals therefore gives
where the sum runs over the retained intervals, which together contain at least objects. Rearranging this inequality gives
where the last step assumes and , so that .
Otherwise, Theorem 8 holds trivially, since . Adding the at most objects with to the bound on , replacing by , and absorbing the constants into proves Theorem 8.
Reduction to -parallelepipeds
In this section, we reduce general convex polyhedra to the -parallelepipeds of § 2. § 4.1 constructs enclosures only a constant factor larger than the objects, with polylogarithmically many pairs 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, denotes the width of a polyhedron in coordinate , and in § 4.1 we assume that all these widths are at most .
Enclosing each object
We can enclose each object in a parallelepiped that lies within a constant enlargement of the object; see Figure 6.

Figure 6. The enclosure of Lemma 12. (a,b) Stretching by gives . (c) inside . (d) The section through the center: (dashed, not to scale).
Lemma 12. Let be a (full-dimensional) convex polyhedron. In polynomial time, we can find a parallelepiped , with edges , , and , where , such that .
Proof. By the algorithmic version of John’s theorem [28] due to Grӧtschel, Lovász, and Schrijver [23], we can, after translating , compute in polynomial time an ellipsoid centered at the origin such that .
An ellipsoid is a stretched ball. Stretching a cube around the ball in the same way gives a parallelepiped around , and since the ball lies in the cube and the cube lies in the ball enlarged by , we get ; see Figure 6(a,b). By rotating the cube before stretching, we can make the edges of have the form , , and with . To be precise, let be the non-singular linear transformation mapping the ball to the ellipsoid . We first pick a unit vector in the preimage . Now has dimension 2, so there exists a vector orthogonal to mapping to this preimage. Finally, picking orthogonal to and , the directions define the edges of the desired rotated cube.
Since and contains the origin, this gives
For each , let be its enclosure from Lemma 12, with positive edge parameters and shears . If the original objects fit in the unit cube, enlarging that packing by a factor of 7 allows each to be placed inside the corresponding enlarged , so the enclosures fit in a cube of side length 7 and satisfy
Their edge coordinates are also , since and all input widths are at most 1.
We next reduce the number of choices for and by rounding and up to the next values in , denoted and , while leaving unchanged. For now, we assume and handle the remaining objects in the proof of Theorem 1.
We now replace by a -parallelepiped with first edge and . Set and , which satisfy because . Scaling and by these factors gives the desired -component and -component , but the third edge’s -component need not be an integer multiple of . We therefore double the second edge and shift the third edge parallel to it; see Figure 7. Choose an integer nearest to and set , so that . The resulting edges of are

Figure 7. Rounding the -shadow (gray) of an enclosure. Doubling the base (blue) and moving the slanted side (red) parallel to it makes its -component a multiple of the new base. The new shadow contains the old one.
The -component of is times that of , so is an -parallelepiped as in § 2, with first edge of length and .
Lemma 13. We have .
Proof. By definition,
and scaling by the factor of 6 gives
Throughout, we use , and .
To prove , we express in terms of :
Hence a point of equals
and since , these coefficients are at most , , and in absolute value. So the point lies in .
To show , we first show . Note that a point of , with , equals
The coefficients of have absolute values at most , less than , and less than , respectively, so the point lies in . Together with Lemma 12, this gives .
Objects with the same rounded pair form a type, giving types since both parameters are rounded in powers of two between and a constant. Moreover, by Lemma 13, so the have coordinate widths .
Lemma 14. Suppose that can be packed into the unit cube. Then, for each type, Algorithm 1 packs the of this type into a box of volume .
Proof. Enlarging a packing of the in the unit cube by a factor of allows us to place each inside the corresponding enlarged , since by Lemma 13, giving a packing in a cube of side . After scaling by , the of each type fit into the unit cube, so Lemmas 7 and 9, together with and , give a packing of volume . Scaling back multiplies the volume by .
Packing general convex polyhedra
Since we do not know the dimensions of an optimal container, we try several candidates. For , let be the largest width of an input object in coordinate , and let be the corresponding side length of an optimal container. Then
The first inequality holds because every object fits into the container.
For the second, stacking all bounding boxes along one axis gives , which yields using the lower bounds in the other two coordinates. We therefore try the candidate containers with side lengths . At least one candidate satisfies in every coordinate. For each candidate, we scale coordinate by to make the container the unit cube. The scaled objects then have coordinate widths at most , 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 , round those with to -parallelepipeds, and pack each of their types with Algorithm 1. For such a candidate, each type is packed into a box of volume 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.
Rounded objects. For each whose enclosure has , we compute the -parallelepiped and pack each type separately with Algorithm 1.
Flat objects. We pack each whose enclosure has into its own bounding box.
Thin objects. We fan-pack the remaining enclosures, which have , as in Algorithm 1, with one object per block.
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 for .
2: for each candidate container with side lengths do
3: Scale coordinate by and compute .
4: Compute for ; pack each type with Algorithm 1. ▷ Step 1
5: Pack with in their bounding boxes. ▷ Step 2
6: Fan-pack with , 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 and . Suppose that objects whose - and -widths are at most and whose -widths are at most are packed by translations into boxes of total volume . In polynomial time, they can be repacked by translations into the box .
Proof. We subdivide each box into cells of length in the - and -directions and in the -direction, and assign each object to the cell containing the corner of its bounding box with the smallest coordinates. We extend each cell by in the - and -directions and by in the -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 and height at most ; see Figure 8.

Figure 8. The repacking of Lemma 15, shown in the plane with the strip extending to the right. (a) Each cell is extended by across the strip and along it, then intersected with its box (outlined for one cell). (b) The extended cells (dotted), of dimensions at most , are packed with their assigned objects into a box of width 1.
Fix a point in an original box. An extended cell containing must have its lower corner in , since its - and -widths are at most and its -width at most . The lower corners lie on a grid with spacings , giving at most choices for each of the first two coordinates and at most for the third. Thus lies in at most 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 .
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 , heights at most , and total volume can be packed by translations in polynomial time into . Packing each extended cell together with its assigned objects therefore gives height at most
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 in every coordinate. After scaling, the optimal packing fits inside the unit cube, and undoing the scaling multiplies volumes by . 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 types is packed into a box of volume . In Step 2, each object fits into a box of dimensions , and these at most boxes can be stacked into the unit cube.
In Step 3, the -shadow of is a parallelogram with edges and , where . As in Algorithm 1, we order the enclosures by increasing slope and translate them so that the bottom edges of their shadows lie in the plane and start at -coordinates . Since the slopes increase with these -coordinates, the shadows have disjoint interiors, so the enclosures do as well. All edge coordinates of the are at most in absolute value, so the enclosures fit into a box with -extent at most , -extent at most , and -extent at most , which has volume .
The boxes of Steps 1–3 therefore have total volume . Since all packed objects have coordinate widths , we scale by a constant to make these widths at most and apply Lemma 15 with in Step 4. This gives a box with base and height , so undoing this constant scaling gives one box of volume . Undoing the original coordinate scaling then multiplies this volume by less than , so the returned packing has volume , and replacing by gives the claimed bound. Finally, there are candidates, each step for a candidate takes polynomial time, and no step depends on , so the same polynomial-time algorithm achieves the bound for every .
We conclude with a remark on the running time. The enclosures are computed only once, since scaling the coordinates maps them to enclosures of the scaled objects. For each of the candidates, all remaining steps take time, apart from the algorithm of Li and Cheng in Lemma 15, which is applied to at most 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 , minimizing the height of the packing.
Proof of Theorem 3. Let be the minimum number of unit cubes and the minimum height. Placing the unit cubes of an optimal bin packing next to each other gives a packing into a box of volume , and an optimal strip packing is itself a packing into a box of volume . Hence and , and the -approximation algorithm gives a packing into a box of volume .
We first consider strip packing. Let be the largest -width of an object, so that . Lemma 15, applied to this box with and , gives a packing into the strip of height at most . Every object fits into an optimal strip packing, so , and the height is at most .
For bin packing, we cut this strip packing, of height , into slabs of length in the -coordinate and assign each object to the slab containing its lowest point. Since now also , each object lies in its slab extended by , which is a box with base and height . We put each extended slab into its own unit cube. Stacking the unit cubes of an optimal bin packing gives a strip packing, so . Since , this uses at most 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 , there exists so that the following holds for all sufficiently small. Let be a set of -tubes contained in the unit ball in , and suppose that every rectangular prism of dimensions contains at most tubes from (this is true, for example, if the tubes in point in -separated directions). For each , let be a measurable set with . Then
Taking and gives a bound on the union of the tubes in which the exponent plays no role. We then remove the restrictions on the tube locations and on .
Proof of Theorem 4. Fix and choose so that Theorem 16 holds for all . The tubes in point in -separated directions, since the unoriented angle between and is at least for .
For , we apply Theorem 16 locally to remove the unit-ball restriction. We partition the space into cubes of side and let consist of the tubes whose segment midpoints lie in a cube . Every point of such a tube is within distance of the centre of , so all tubes in lie in the unit ball centred there. The theorem therefore applies to each with and .
Each point lies in at most of these unit balls, since their centres must lie in , which contains at most points of the grid of spacing . Consequently,
For , we bound the number of tubes by placing a cap of angular radius around each on . The caps have disjoint interiors, since the angles between the are at least , and each has area , using for . Comparing their total area with the sphere’s area gives at most tubes. Since their union contains the largest tube and , we obtain
Taking proves Theorem 4. Thus depends on only through .
Polylogarithmic bounds
The factor in Theorem 1 arises solely from the 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 [38 Corollary 9.1], whereas the formalization verifies a bound with a loss of . We show that these bounds yield approximation ratios and , respectively.
The tube estimates
Theorem 17 ([37 tube-union-logarithmic]). *There is a constant such that, for all , all with for , and all ,
The formalization states this bound in , with in the numerator and exponent , which equals 66 for ; this statement does not seem to appear in [38]. As we will show, it yields Theorem 4 with the factor replaced by for some absolute constant . Here we absorb the additive 1 in the logarithmic factor into , using .
Theorem 17 requires the Euclidean distance between any two direction vectors to be at least the tube radius, whereas our angular separation guarantees only . We therefore replace each by , reducing its radius to . 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 .
The preprint [38] instead claims a Kakeya maximal estimate, formulated using the Kakeya maximal function , defined for a locally integrable function by
Thus is the supremum of the averages of over tubes of length 1 and radius in direction . For example, if is a union of such tubes and , then whenever one of the tubes has direction . For nearby directions, a tube still lies largely in , so remains close to 1. We measure and using the norms
We write for the space of functions with finite norm. For an indicator function , this norm is .
Theorem 18 [38 Corollary 9.1]. There is a constant such that, for all and all ,
The preprint states this estimate in for every , with the norms and the power , where ; for , this is the power above.
Lemma 19. If Theorem 18 holds, then, for , the logarithmic factor in Theorem 17 can be replaced by .
Proof. Let and let and be as in Theorem 17. Write and , and for each define the cap of angular radius centred at by
These caps are disjoint. Indeed, suppose that lies in both and . Angles between unit vectors satisfy the triangle inequality, so the angle between and is
Since a chord of the unit circle is shorter than the corresponding arc, , contradicting the assumption .
A cap of angular radius has area . Since for , each has area at least
We claim that for every . Let . Then and . Moreover, . Indeed, let be a point of , with and . Since , its distance to the point of the axis segment of is at most
Hence covers at least of the tube , which gives .
We now bound from both sides:
Rearranging gives the claimed bound with .
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 by . We trace this change through the three steps of the analysis.
First, Theorem 8 holds with replaced by . Indeed, the volume bound of § 3, with and the new factor, shows that at most
objects have . If , then , so this number is ; if , then anyway. Together with the at most objects with , this gives .
Second, with this bound, the computation in the proof of Lemma 9 gives
so, by the proof of Lemma 14, each type is packed into a box of volume .
Finally, there are types, so the boxes of Steps 1–3 in the proof of Theorem 1 have total volume . The rest of that proof is unchanged, so the returned packing has volume .
If Theorem 18 holds, then by Lemma 19 the same argument works with the exponent replaced by throughout, which gives the approximation ratio . □
References
- [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]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]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]Helmut Alt. Computational Aspects of Packing Problems. Bull. EATCS, 118, 2016.
- [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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]Keqin Li and Kam-Hoi Cheng. On Three-Dimensional Packing. SIAM J. Comput., 19(5):847–867, 1990. doi:10.1137/0219059.DOI
- [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]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]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]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]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]Nadja Seiferth. Algorithmic Aspects of Packing Problems. PhD thesis, FU Berlin, Germany, 2022. doi:10.17169/refubium-35132.DOI
- [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
