I will assume you are asking for an exact cover by nonexterior squares, as in my comment.

An old paper of mine, "Covering orthogonal polygons with squares," 1988 (link here), addresses a special case: both the polygon edges and the square sides are parallel to coordinate axes. Our result was subsequently improved by Bar-Yehuda and Ben-Hanoch (Internat. Journal of Computational Geometry & Applications, Vol. 6, No. 1, 1996; World Scientific link).

For arbitrary polygons (and arbitrary square orientations), the problem (as I have interpreted it) is not solvable, because any acute angle cannot be covered. For polygons with no acute angles, this problem has been extensively studied, partly for its application to VLSI masking. I recommend looking at the 1997 paper, "Approximation algorithms for covering polygons with squares and similar problems" by Levcopoulos and Gudmundsson (Springer link). They achieve a constant-factor approximation with a roughly quadratic algorithm. They also provide a useful summary of related work in their Introduction.

I will assume you are asking for an exact cover by nonexterior squares, as in my comment.

An old paper of mine, "Covering orthogonal polygons with squares," 1988 (link here), addresses a special case: both the polygon edges and the square sides are parallel to coordinate axes. Our result was subsequently improved by Bar-Yehuda and Ben-Hanoch (Internat. Journal of Computational Geometry & Applications, Vol. 6, No. 1, 1996; World Scientific link).

For arbitrary polygons (and arbitrary square orientations), the problem (as I have interpreted it) is not solvable, because any acute angle cannot be covered. For polygons with no acute angles, this problem has been extensively studied, partly for its application to VLSI masking. I recommend looking at the 1997 paper, "Approximation algorithms for covering polygons with squares and similar problems" by Levcopoulos and Gudmundsson (Springer link). They achieve a constant-factor approximation with a roughly quadratic algorithm. They also provide a useful summary of related work in their Introduction.

I will assume you are asking for an exact cover by nonexterior squares, as in my comment.

An old paper of mine, "Covering orthogonal polygons with squares," 1988 (link here), addresses a special case: both the polygon edges and the square sides are parallel to coordinate axes. Our result was subsequently improved by Bar-Yehuda and Ben-Hanoch (Internat. Journal of Computational Geometry & Applications, Vol. 6, No. 1, 1996; World Scientific link).

For arbitrary polygons (and arbitrary square orientations), the problem (as I have interpreted it) is not solvable, because any acute angle cannot be covered. For polygons with no acute angles, this problem has been extensively studied, partly for its application to VLSI masking. I recommend looking at the 1997 paper, "Approximation algorithms for covering polygons with squares and similar problems" by Levcopoulos and Gudmundsson (Springer link). They achieve a constant-factor approximation with a roughly quadratic algorithm. They also provide a useful summary of related work in their Introduction.

I will assume you are asking for an exact cover by nonexterior squares, as in my comment.

An old paper of mine, "Covering orthogonal polygons with squares," 1988 (link here), addresses a special case: both the polygon edges and the square sides are parallel to coordinate axes. Our result was subsequently improved by Bar-Yehuda and Ben-Hanoch (Internat. Journal of Computational Geometry & Applications, Vol. 6, No. 1, 1996; World Scientific link).

For arbitrary polygons (and arbitrary square orientations), the problem (as I have interpreted it) is not solvable, because any acute angle cannot be covered. For polygons with no acute angles, this problem has been extensively studied, partly for its application to VLSI masking. I recommend looking at the 1997 paper, "Approximation algorithms for covering polygons with squares and similar problems" by Levcopoulos and Gudmundsson (Springer link). They achieve a constant-factor approximation with a roughly quadratic algorithm. They also provide a useful summary of related work in their Introduction.