computational geometrycoveringdiscrete geometrymg.metric-geometry
I have a problem whereby, given an arbitrary polygon with any number of points, I need to cover the whole area by a number of fixed size squares. I can easily find a set of squares which covers the polygon but I need to ensure that I find the minimum number of squares.
Can anyone suggest a good method to do this?
Thanks in advance.
This problem and variants were extensively explored in the paper "Optimal Covering Tours with Turn Costs," by Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sandor P. Fekete, Joseph S. B. Mitchell, Saurabh Sethia, SIAM Journal on Computing, volume 35, number 3, 2005, pages 531–566. (Link to preliminary 2003 arXiv version).
We prove that the covering tour problem with turn costs is NP-complete, even if the objective is purely to minimize the number of turns, the pocket is orthogonal (rectilinear), and the cutter must move axis-parallel. The hardness of the problem is not apparent, as our problem seemingly bears a close resemblance to the polynomially solvable Chinese postman problem; ...
Almost every variant is NP-complete/hard, so the concentration has been on approximations.
To give a sense of the bewildering variety of results, here is a table from the above paper:
This paper has 45 references, and surveys related milling and lawnmowing results.
Here is one relevant result, by Michael Hoffmann,
"Covering polygons with few rectangles," 2001. (PDF download link)
He shows that minimal covering by two or three congruent axis-aligned rectangles of a collection
of polygons with a total of $n$ vertices
can be found in $O(n)$ time.
He also says that the more general problem—covering a set of polygons by $p>3$ congruent rectangles—cannot be approximated by better than a factor of $2$ unless $P=NP$ (because of the relation to the $p$-center problem). He does not directly address covering just one polygon, or with covering by incongruent rectangles.
This latter problem (your problem) is partially addressed computationally in the paper 2011, "Covering a polygonal region by rectangles," Computational Optimization and Applications (Springer link). It appears that they start with a set of rectangles, and extend them until they form a cover.
Best Answer
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.