Given an arbitrary polygon, and a grid square size x, I'd want to find a placement of the polygon such that it covers the minimum amount of cells in the grid.
The polygon can be translated vertically and horizontally, but not rotated or scaled.
2 example solutions for the grey polygon
A greedy algorithm could be to determine the bounding box of the polygon, then start at the top left corner and add squares vertically and horizontally until the bounding box is covered. Then, count the squares that intersect the polygon.
As illustrated in the image, that strategy is not optimal, as we can translate the polygon in the example so we only need 17 squares instead of 18.
I have a strong suspicion that the problem is not in P.
