2026-08-10T17:38:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20028 2024-06-06T06:21:17Z ddc:004 open_access

Computing Maximum Polygonal Packings in Convex Polygons Using Best-Fit, Genetic Algorithms and ILPs (CG Challenge) Atak, Alkan Buchin, Kevin Hagedoorn, Mart Heinrichs, Jona Hogreve, Karsten Li, Guangping Pawelczyk, Patrick Polygon Packing Nesting Problem Genetic Algorithm Integer Linear Programming 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alkan Atak and Kevin Buchin and Mart Hagedoorn and Jona Heinrichs and Karsten Hogreve and Guangping Li and Patrick Pawelczyk 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.83 urn:nbn:de:0030-drops-200283 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.83 eng https://creativecommons.org/licenses/by/4.0/legalcode