Densest translational lattice packing of non-convex polygons

A translational lattice packing of k polygons P-1, P-2, P-3,..., P-k, is a (non-overlapping) packing of the k polygons which is replicated without overlap at each point of a lattice i(0)nu(0) + i(1)nu(1), where nu(0) and v(1) are vectors generating the lattice and i(0) and i(1) range over all integers. A densest translational lattice packing is one which minimizes the area \nu(0) x nu(1)\ of the fundamental parallelogram. An algorithm and implementation is given for densest translational lattice packing. This algorithm has useful applications in industry, particularly clothing manufacture. (C) 2001 Elsevier Science B.V. All rights reserved.