1
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ I think you need to sharpen the description of your problem: one large square can cover any polygon. Perhaps you mean: the union of the squares must be exactly the polygon, but no square can contain a point exterior to the polygon? $\endgroup$
    – Joseph O'Rourke
    Commented Mar 15, 2012 at 13:50
  • $\begingroup$ I agree with Joseph. Is the size of the squares fixed before the polygon is given? Are you allowing the squares to be rotated, or must they have sides parallel to the axes? $\endgroup$
    – Lee Mosher
    Commented Mar 15, 2012 at 13:53
  • $\begingroup$ Apologies for the lack of clarity on my question. The polygon I wish to cover can be any size and shape. My squares are always smaller than the main polygon and of a fixed size. Therefore one bounding square will not work. The squares must also be upright (i.e. they cant be rotated). The union of all my squares must cover the completely to main polygon and I'm looking to find the minimum number of squares. The union of squares can include points exterior to the polygon. $\endgroup$
    – Chris
    Commented Mar 15, 2012 at 15:37
  • $\begingroup$ There remains one additional under-specified aspect: May the squares overlap one another? Or are they to be arranged in a grid? $\endgroup$
    – Joseph O'Rourke
    Commented Mar 16, 2012 at 0:40
  • $\begingroup$ They can overlap. $\endgroup$
    – Chris
    Commented Mar 17, 2012 at 21:59

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ There is also this 1998 paper: duch.mimuw.edu.pl/~kowaluk/TOMEK/106-108.pdf "A better approximation algorithm for covering polygons with squares", by Grazyna Zwozniak, which improves upon Levcopoulos and Gudmundsson's results. $\endgroup$
    – Erel Segal-Halevi
    Commented Jul 11, 2013 at 22:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .