← 研踪 PaperTrailarXiv:2611.26352 · v1
Polylogarithmic Approximation for Packing Convex Polyhedra
凸多面体装箱问题的多对数近似算法
首次提交 2026-11-20 00:24
版本更新 2026-11-20 00:24
雷达观测 2026-11-20 12:52
摘要
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.
作者备注:28 pages, 8 figures
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-20 00:24 · 最新观测版本
Polylogarithmic Approximation for Packing Convex Polyhedra
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.
查看此版本解读 →查看此版本原文 ↗