Suppose I have an arbitrary number of adjacent 1×1 squares on a grid (Adjacent defined as "each square shares at least one side with another"). I'm looking for a good way to find the minimal number of (possibly overlapping) rectangles that cover all the squares exactly. This is, the union of all the rectangles has the exact same shape and size as the union of all the squares.
For example, the L tetromino can be covered with two rectangles (3×1;2×1, 2×1;2×1 or 3×1;1×1).
In my instance of the problem I need to find a specific arrangement of rectangles so that I can test if a point is inside the shape. What I'm really looking for is an algorithm that efficiently (polynomial time) finds a covering where the number of rectangles is less than 2n (n being the optimal covering).
Best Answer
Here's an $16$-approximation, assuming the object does not have holes. In particular, this approximation gives disjoint rectangles, and thus, is an instance of a Polygon Covering (nevertheless the bounds hold).
The union of the squares can be alternatively seen as a rectilinear polygon. We let the vertices of the polygon be the sharp points on the boundary of the polygon. Let $V$ be the number of such vertices. I will describe an approach based on the sweep-line triangulation algorithm. Basically, I will give a trivial triangulation if the polygon is monotone, and will later describe how to transform the polygon into monotone pieces.
If the polygon is monotone and does not have holes
First, let's consider what happens if the polygon is monotone (in $y$ coordinates) and have no holes. Let $P$ be the optimal number of rectangles to cover this polygon. First, I claim that
$$4P \le V$$
That is, $V$ is at most $4$ times the number of rectangles in the optimal answer. To see this, consider any rectangle covering the object. What is the maximum number of vertices this rectangle can touch? The answer is $4$ and thus, the bound follows.
Now, we can construct $V$ rectangles that cover everything as follows: Let $Y$ be the sorted list of distinct $y$ coordinates of the vertices of the polygon. For every pair of adjacent $y_i \in Y, y_{i+1} \in Y$, construct a rectangle to cover the polygon. Clearly this constructs at most $V$ rectangles.
Making the polygon monotone
We do a similar approach with triangulation: we make the polygon monotone and cover each monotone piece by rectangles. We can do monotonizing in a similar approach as in triangulation (alluded in the wiki): whenever we encounter a concave point that "faces down", we draw a line from the point left and right until we hit the boundaries of the polygon, and cut the polygon there, creating separate polygons in the process (it really is similar to the algorithm described in the wiki, but instead of connecting it to the vertex in the left/right sides of the polygon, we create a new vertex in the corresponding boundary). Thus, each "concave" point may create at most $2$ new vertices, and the $12$-approximation follows.
Now, how many concave points can a rectilinear polygon has? It is at most the number of convex points it have (in fact, it is exactly $4$ more than that). Now, if $V_x$ is the number of convex vertices of the polygon, using a similar reasoning as before, we have $4P \le V_x$, and thus, this is a $4 \times (1+3) = 16$-approx algorithm.
What if the polygon has holes?
The bounds on the optimal answer no longer holds, and thus, no guarantee is present even if we were to monotonize the polygon using the vertices of the holes.