Watson, P. D.; Tobias, A. M. An efficient algorithm for the regular \(W_1\) packing of polygons in the infinite plane. (English) Zbl 1054.90626 J. Oper. Res. Soc. 50, No. 10, 1054-1062 (1999). Summary: This paper describes a new algorithm, PLANEPACK, which determines an optimal or near optimal solution for the \(W_1\) 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. Cited in 4 Documents MSC: 90C27 Combinatorial optimization 90C59 Approximation methods and heuristics in mathematical programming Keywords:packing; heuristics; optimisation; non-convex polygon PDFBibTeX XMLCite \textit{P. D. Watson} and \textit{A. M. Tobias}, J. Oper. Res. Soc. 50, No. 10, 1054--1062 (1999; Zbl 1054.90626)