Search Results

Documents authored by Heinrichs, Jona

Document
CG Challenge
DOI: 10.4230/LIPIcs.SoCG.2024.83
Computing Maximum Polygonal Packings in Convex Polygons Using Best-Fit, Genetic Algorithms and ILPs (CG Challenge)

Authors: Alkan Atak, Kevin Buchin, Mart Hagedoorn, Jona Heinrichs, Karsten Hogreve, Guangping Li, and Patrick Pawelczyk

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
Given a convex region P and a set of irregular polygons with associated profits, the Maximum Polygon Packing Problem seeks a non-overlapping packing of a subset of the polygons (without rotations) into P maximizing the profit of the packed polygons. Depending on the size of an instance, we use different algorithmic solutions: integer linear programs for small instances, genetic algorithms for medium-sized instances and a best-fit approach for large instances. For packing rectilinear polygons we provide a dedicated best-fit algorithm.
Cite as

Alkan Atak, Kevin Buchin, Mart Hagedoorn, Jona Heinrichs, Karsten Hogreve, Guangping Li, and Patrick Pawelczyk. Computing Maximum Polygonal Packings in Convex Polygons Using Best-Fit, Genetic Algorithms and ILPs (CG Challenge). In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 83:1-83:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{atak_et_al:LIPIcs.SoCG.2024.83,
  author =	{Atak, Alkan and Buchin, Kevin and Hagedoorn, Mart and Heinrichs, Jona and Hogreve, Karsten and Li, Guangping and Pawelczyk, Patrick},
  title =	{{Computing Maximum Polygonal Packings in Convex Polygons Using Best-Fit, Genetic Algorithms and ILPs}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{83:1--83:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.83},
  URN =		{urn:nbn:de:0030-drops-200283},
  doi =		{10.4230/LIPIcs.SoCG.2024.83},
  annote =	{Keywords: Polygon Packing, Nesting Problem, Genetic Algorithm, Integer Linear Programming}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact