2016/01/18 by Helmut G. Alt, Helmut Alt, Alt, Helmut +2
Computer Science · Engineering · Materials Science · #Advanced Manufacturing and Logistics Optimization #Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences #Optimization and Packing Problems #biodegradable polymer synthesis and properties #cs.CG
paper · pdf · doi:10.48550/arxiv.1601.04585
arxiv created 2016/01/18 · openalex publication_date 2016/01/18 · arxiv updated 2016/01/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate the problem of computing a minimal-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 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 minimal volume containers for the objects described.