Approximating Smallest Containers for Packing Three-Dimensional Convex Objects

DOI10.1142/S0218195918600026zbMATH Open1397.68194arXiv1601.04585WikidataQ129562383 ScholiaQ129562383MaRDI QIDQ3177900FDOQ3177900

Authors: Helmut Alt, Nadja Scharf 

Publication date: 2 August 2018

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1601.04585

Recommendations

• scientific article; zbMATH DE number 6861944
• Approximating minimum-area rectangular and convex containers for packing convex polygons
• scientific article; zbMATH DE number 6698326
• 3-D container packing heuristics
• scientific article; zbMATH DE number 773158
• Minimization of the container for packing of three cubes in dimension 4
• AN EFFICIENT APPROACH FOR THE THREE-DIMENSIONAL CONTAINER PACKING PROBLEM WITH PRACTICAL CONSTRAINTS
• Packing convex 3D objects with special geometric and balancing conditions
• A packing algorithm for three-dimensional convex particles

zbMATH Keywords

approximation algorithmcomputational geometrypacking

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Computational aspects related to convexity (52B55)

Cites Work

• A Compactness Theorem For Affine Equivalence-Classes of Convex Regions
• A near-optimal solution to a two-dimensional cutting stock problem
• A new asymptotic approximation algorithm for 3-dimensional strip packing
• Improved approximation algorithm for two-dimensional bin packing
• Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
• Title not available (Why is that?)
• Three-dimensional packings with rotations
• Approximating minimum-area rectangular and convex containers for packing convex polygons
• An optimal deterministic algorithm for computing the diameter of a three-dimensional point set

Cited In (8)

• Title not available (Why is that?)
• Packing 2D disks into a 3D container
• Approximating minimum-area rectangular and convex containers for packing convex polygons
• Title not available (Why is that?)
• A Multi-sphere Scheme for 2D and 3D Packing Problems
• Modeling close packing of 3D objects
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: Approximating Smallest Containers for Packing Three-Dimensional Convex Objects

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177900)