DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2016.11

Approximating Smallest Containers for Packing Three-Dimensional Convex Objects

Authors: Helmut Alt and Nadja Scharf

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract

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.

Cite as

Helmut Alt and Nadja Scharf. Approximating Smallest Containers for Packing Three-Dimensional Convex Objects. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{alt_et_al:LIPIcs.ISAAC.2016.11,
  author =	{Alt, Helmut and Scharf, Nadja},
  title =	{{Approximating Smallest Containers for Packing Three-Dimensional Convex Objects}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.11},
  URN =		{urn:nbn:de:0030-drops-67801},
  doi =		{10.4230/LIPIcs.ISAAC.2016.11},
  annote =	{Keywords: computational geometry, packing, approximation algorithm}
}

Search Results

Documents authored by Scharf, Nadja

Approximating Smallest Containers for Packing Three-Dimensional Convex Objects

Abstract

Cite as

Thanks for your feedback!

Could not send message