DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2023.76

Improved Approximations for Translational Packing of Convex Polygons

Authors: Adam Kurpisz and Silvan Suter

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract

Optimal packing of objects in containers is a critical problem in various real-life and industrial applications. This paper investigates the two-dimensional packing of convex polygons without rotations, where only translations are allowed. We study different settings depending on the type of containers used, including minimizing the number of containers or the size of the container based on an objective function. Building on prior research in the field, we develop polynomial-time algorithms with improved approximation guarantees upon the best-known results by Alt, de Berg and Knauer, as well as Aamand, Abrahamsen, Beretta and Kleist, for problems such as Polygon Area Minimization, Polygon Perimeter Minimization, Polygon Strip Packing, and Polygon Bin Packing. Our approach utilizes a sequence of object transformations that allows sorting by height and orientation, thus enhancing the effectiveness of shelf packing algorithms for polygon packing problems. In addition, we present efficient approximation algorithms for special cases of the Polygon Bin Packing problem, progressing toward solving an open question concerning an 𝒪(1)-approximation algorithm for arbitrary polygons.

Cite as

Adam Kurpisz and Silvan Suter. Improved Approximations for Translational Packing of Convex Polygons. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 76:1-76:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kurpisz_et_al:LIPIcs.ESA.2023.76,
  author =	{Kurpisz, Adam and Suter, Silvan},
  title =	{{Improved Approximations for Translational Packing of Convex Polygons}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{76:1--76:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.76},
  URN =		{urn:nbn:de:0030-drops-187299},
  doi =		{10.4230/LIPIcs.ESA.2023.76},
  annote =	{Keywords: Approximation algorithms, Packing problems, Convex polygons, Bin packing, Strip packing, Area minimization}
}

Search Results

Documents authored by Suter, Silvan

Improved Approximations for Translational Packing of Convex Polygons

Abstract

Cite as

Thanks for your feedback!

Could not send message