An efficient algorithm for the regular w\ packing of polygons in the infinite plane

Research output: Contribution to journalArticlepeer-review


Colleges, School and Institutes


This paper describes a new algorithm, PLANEPACK, which determines an optimal or near optimal solution for the Wj packing of identical shapes in the infinite plane. Restricted to polygons for computational convenience, it is based on the no-fit polygon/configuration space obstacle approach. The algorithm was tested on a modest set of fourteen polygons (thirteen non-interlocking and one interlocking) and yielded a feasible solution for each. The solutions were optimal for four of the non-interlocking polygons and near optimal for the other nine. As expected though, the solution for the one interlocking polygon was sub-optimal and enhancements to the algorithm would be required for such cases.


Original languageEnglish
Pages (from-to)1054-1062
Number of pages9
JournalOperational Research Society. Journal
Issue number10
Publication statusPublished - 1999


  • Heuristics, Non-convex polygon, Optimisation, Packing