On rectangular covering problems

Many applications like picture processing, data compression or pattern recognition require a covering of a set of points most often located in the (discrete) plane by rectangles due to specific cost constraints. In this paper we provide exact dynamic programming algorithms for covering point sets by regular rectangles, that have to obey certain (parameterized) boundary conditions. The concrete representative out of a class of objective functions that is studied is to minimize sum of area, circumference and number of patches used. This objective function may be motivated by requirements of numerically solving PDE's by discretization over (adaptive multi-)grids. More precisely, we propose exact deterministic algorithms for such problems based on a (set theoretic) dynamic programming approach yielding a time bound of O(n^23^n) . In a second step this bound is (asymptotically) decreased to O(n^62^n) by exploiting the underlying rectangular and lattice structures. Finally, a generalization of the problem and its solution methods is discussed for the case of arbitrary (finite) space dimension