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_0v_0 + i_1v_1, where v_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 |v_0 * v_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.