Optimally Decomposing Coverings with Translates of a Convex Polygon
We show that any k-fold covering using translates of an arbitrary convex polygon can be decomposed into Omega(k) covers. Such a decomposition can be computed using an efficient (polynomial-time) algorithm.
cover decomposability geometric set cover