Approximating Smallest Containers for Packing Three-Dimensional Convex Objects

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

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

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

• Title not available (Why is that?)
• 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
• 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 (3)

• Title not available (Why is that?)
• Modeling close packing of 3D objects
• Title not available (Why is that?)

Recommendations

• Packing Convex 3D Objects with Special Geometric and Balancing Conditions 👍 👎
• A packing algorithm for three-dimensional convex particles 👍 👎
• Minimization of the container for packing of three cubes in dimension 4 👍 👎
• 3-D container packing heuristics 👍 👎
• Approximating Minimum-Area Rectangular and Convex Containers for Packing Convex Polygons 👍 👎
• AN EFFICIENT APPROACH FOR THE THREE-DIMENSIONAL CONTAINER PACKING PROBLEM WITH PRACTICAL CONSTRAINTS 👍 👎
• Title not available (Why is that?) 👍 👎
• 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)