DROPS

Document

CG Challenge

DOI: 10.4230/LIPIcs.SoCG.2024.86

A General Heuristic Approach for Maximum Polygon Packing (CG Challenge)

Authors: Canhui Luo, Zhouxing Su, and Zhipeng Lü

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

Abstract

This work proposes a general heuristic packing approach to address the Maximum Polygon Packing Problem introduced by the CG:SHOP 2024 Challenge. Our solver primarily consists of two steps: (1) Partitioning the container and polygons to form a series of small-scale subproblems; (2) For each subproblem, sequentially placing polygons into the container and attempting to eliminate overlaps.

Cite as

Canhui Luo, Zhouxing Su, and Zhipeng Lü. A General Heuristic Approach for Maximum Polygon Packing (CG Challenge). In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 86:1-86:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{luo_et_al:LIPIcs.SoCG.2024.86,
  author =	{Luo, Canhui and Su, Zhouxing and L\"{u}, Zhipeng},
  title =	{{A General Heuristic Approach for Maximum Polygon Packing}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{86:1--86: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.86},
  URN =		{urn:nbn:de:0030-drops-200315},
  doi =		{10.4230/LIPIcs.SoCG.2024.86},
  annote =	{Keywords: packing, polygon, heuristic, differential evolution, local search, tabu search}
}

Search Results

Documents authored by Lü, Zhipeng

A General Heuristic Approach for Maximum Polygon Packing (CG Challenge)

Abstract

Cite as

Thanks for your feedback!

Could not send message