Covering a square with crosses

Question

I am trying to find the smallest number of "crosses" needed to cover an n by n square with overlap.
A "cross" is basically the "X" pentomino, the following figure:



The problem is to place the smallest number of crosses so that each cell is covered at least once.
The crosses are placed by picking the point for their center. They may overlap with each other and
they do not have to fit entirely on the board - for example, you can place a cross at the cell $(0,0)$.
Which would produce the following:



I would like to know whether there exists a polynomial-time algorithm for finding an optimal solution (finding the positions of the crosses). Clearly there are some patterns that achieve a good covering, but I would like to have a proof or decent argument why such a covering is the best possible.
I have checked $n = 1,2,3,4,5,6,7$. The minimal number of crosses are: $1,2,3,4,7,10,12$
Here are some examples of how such coverings might be achieved (green cells are the centers of the crosses):