2026-07-21T21:12:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6780 2024-03-06T10:38:52Z ddc:004 open_access

Approximating Smallest Containers for Packing Three-Dimensional Convex Objects Alt, Helmut Scharf, Nadja computational geometry packing approximation algorithm We investigate the problem of computing a minimum-volume container for the non-overlapping packing of a given set of three-dimensional convex objects. Already the simplest versions of the problem are NP-hard so that we cannot expect to find exact polynomial time algorithms. We give constant ratio approximation algorithms for packing axis-parallel (rectangular) cuboids under translation into an axis-parallel (rectangular) cuboid as container, for packing cuboids under rigid motions into an axis-parallel cuboid or into an arbitrary convex container, and for packing convex polyhedra under rigid motions into an axis-parallel cuboid or arbitrary convex container. This work gives the first approximability results for the computation of minimum volume containers for the objects described. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Helmut Alt and Nadja Scharf 2016 Is Part Of LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2016.11 urn:nbn:de:0030-drops-67801 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.11 eng https://creativecommons.org/licenses/by/3.0/legalcode