About the "covering problem"

Factual Questions
1

A friend of mine told me he think he came up with an algorithm for solving the covering problem. He asked for my help in demonstrating / proving it.

The covering problem (or at least the variant I’m dealing with) is: given an area composed of squares (the area may be any shape, connected), and a cell, also composed of squares, what is the minimal number of cells needed to cover the whole area?
A simple example of the covering problem I was presented with may be this:
Take a chess board, with N (N>=0) of its squares removed, but in such a way that it’s still connected (one area).
Now, take a simple shape – say a domino like 1X2 element, or a cross-like element (a center piece, and its immediate neighbors to the E, W, S, N).
How many elements are required to cover the whole area?
elements may overlap, and they may “cover” squares outside of the area. They may not be turned, though.

Someone on another board I frequent suggested it is similar to the set cover problem. Are the two problems identical? If not, is it a well-known problem? Is it NP or P? Are there any / many algorithms to solve it?

Thanks!

2

From my reading of the Wikipedia link there, I think that the only difference is that the Set Cover problem assumes that the little guys you’re trying to cover the area with can exactly cover the area (i.e. no overlaps or overhangs.)

I’m not sure if that invalidates it’s NP-ness. But I would have to imagine that it’s an easier problem than Set Cover.

3

It’s similar to the set cover problem, but instances of this may have solutions where an instance of the set cover problem would not. It’s not at all clear that that makes it simpler.

The difficulty in the proof will be precisely defining the notion of squares outside the area, which means that you can’t exactly use the methods related to the set cover problem. I’d try representing the set to be covered as elements of Z[sup]2[/sup].