Packing and covering the plane with translates of a convex polygon

TitlePacking and covering the plane with translates of a convex polygon
Publication TypeJournal Articles
Year of Publication1990
AuthorsMount D, Silverman R
JournalJournal of Algorithms
Volume11
Issue4
Pagination564 - 580
Date Published1990/12//
ISBN Number0196-6774
Abstract

A covering of the Euclidean plane by a polygon P is a system of translated copies of P whose union is the plane, and a packing of P in the plane is a system of translated copies of P whose interiors are disjoint. A lattice covering is a covering in which the translates are defined by the points of a lattice, and a lattice packing is defined similarly. We show that, given a convex polygon P with n vertices, the densest lattice packing of P in the plane can be found in O(n) time. We also show that the sparsest lattice covering of the plane by a centrally symmetric convex polygon can be solved in O(n) time. Our approach utilizes results from classical geometry that reduce these packing and covering problems to the problems of finding certain extremal enclosed figures within the polygon.

URLhttp://www.sciencedirect.com/science/article/pii/019667749090010C
DOI10.1016/0196-6774(90)90010-C