Approximating Smallest Containers for Packing Three-Dimensional Convex Objects

DOI10.1142/S0218195918600026MaRDI QIDQ3177900zbMATH OpenWikidataFDO

Authors Helmut Alt, Nadja Scharf

Publication date 2 August 2018

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3289061 (Why is no real title available?)
• 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
• An optimal deterministic algorithm for computing the diameter of a three-dimensional point set
• Approximating minimum-area rectangular and convex containers for packing convex polygons
• Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
• Improved approximation algorithm for two-dimensional bin packing
• Three-dimensional packings with rotations

Cited in

(8)

• scientific article; zbMATH DE number 2205697 (Why is no real title available?)
• Packing 2D disks into a 3D container
• scientific article; zbMATH DE number 4180839 (Why is no real title available?)
• A Multi-sphere Scheme for 2D and 3D Packing Problems
• scientific article; zbMATH DE number 6861944 (Why is no real title available?)
• Approximating minimum-area rectangular and convex containers for packing convex polygons
• scientific article; zbMATH DE number 6698326 (Why is no real title available?)
• Modeling close packing of 3D objects

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)