<p>This is a variant of geometric set cover. Depending on the exact settings, you might be able to do some good approximation. The problem is of course NP-Hard. The natural huersitics are to use greedy algorithm (always pick the rectangle/strip that covers the most area not covered yet. The alternative technique is to use reweighing. There are some interesting theoretical results, but frankly, nothing that should be too useful in practice. One interesting hueristic you might want to try, is to first decompose your polygon into minimal number of convex shapes (using Keil dynamic programming algorithm), and then covering each convex polygon separately...</p>

CC BY-SA 3.0
2012-12-04T14:37:51.637Z
I'm not familiar with the Keil Dynamic Programming algorithm. However, I did find a method to work using a combination of the Largest-Inscribed Rectangle and Minimum-Bounding Rectangle algorithms with some variants based upon heuristics.
Josh C.
CC BY-SA 3.0
2012-12-01T05:56:24.853Z
2012-12-01T05:56:24.853Z
Sariel Har-Peled
<p>I think <a href="http://www.cs.helsinki.fi/u/polishch/pages/suit.pdf" rel="nofollow">this paper</a> may be of some help.  Obviously it's not the same problem--in fact it's the reverse problem, covering a rectangle with polygons--but some of the ideas could be a starting point.  In particular, this reverse problem is NP-hard and I suspect yours may be as well (though there's no obvious extension of the reduction as far as I can tell).</p>

<p>E. Arkin, A. Efrat, G. Hart, I. Kostitsyna, A. Kroller, J. Mitchell, and V. Polishchuk. Scandinavian Thins on Top of Cake: On the Smallest One-Size-Fits-All Box.
<em>Fun with Algorithms</em>. pg.16-27.  2012</p>

CC BY-SA 3.0
2012-08-23T17:10:01.940Z
Thank you for your suggestion. I've been working with the engineering and manufacturing departments at my company to bring more clarificaiton to this problem. I am still waiting to confirm, but I am now thinking an algorithm that would return sets of largest inscribed rectangles would work. While it does not completely cover the shape, it would give preference to the orthognal regions while leaving the non-orthogonal regions to some heuristics. The only trick is to maxamize those orthogonal regions. See my last image with the 9 lamda-like figures.
Josh C.
CC BY-SA 3.0
2012-08-23T17:00:38.577Z
2012-08-23T17:00:38.577Z
SamM
<p>I am trying to cover a simple concave polygon with a minimum rectangles. My rectangles can be any length, but they have maximum widths, and the polygon will never have an acute angle.</p>

<p>I thought about trying to decompose my concave polygon into triangles that produce a set of minimumally overlapping rectangles minimally bounding each triangle and then merging those rectangles into larger ones. However, I don't think this will work for small notches in the edges of the polygon. The triangles created by the reflex vertices on those notches will create the wrong rectangles. I am looking for rectangles that will span/ignore notches. </p>

<p>I don't really know anything about computational geometry, so I'm not really sure on how to begin asking the question.</p>

<p>I found other posts that were similar, but not what I need:</p>

<ul>
<li><a href="https://mathoverflow.net/questions/28303/split-polygon-into-minimum-amount-of-rectangles-and-triangles">split polygon into minimum amount of rectangles and triangles</a></li>
<li><a href="https://mathoverflow.net/questions/91279/covering-an-arbitrary-polygon-with-minimum-number-of-squares">Covering an arbitrary polygon with minimum number of squares</a></li>
<li><a href="https://stackoverflow.com/questions/3476778/find-k-rectangles-so-that-they-cover-the-maximum-number-of-points">Find $k$ rectangles so that they cover the maximum number of points</a></li>
<li><a href="https://stackoverflow.com/questions/5919298/algorithm-for-finding-the-fewest-rectangles-to-cover-a-set-of-rectangles">Algorithm for finding the fewest rectangles to cover a set of rectangles</a></li>
</ul>

<p>Some examples: Black is the input. Red is the acceptable output.</p>

<p><img src="https://i.sstatic.net/0NDBF.png" alt="enter image description here"></p>

<p>Another exmaple: The second output is prefered. However, generating both outputs and using another factor to determine preference is probably necessary and not the responsibility of this algorithm.</p>

<p><img src="https://i.sstatic.net/9qgeJ.png" alt="enter image description here"></p>

<p><img src="https://i.sstatic.net/n02UR.png" alt="enter image description here"></p>

<p>Polygons that mimic curves are extremely rare. In this scenario much of the area of the rectangles is wasted. However, this is acceptable because each rectangle obeys the max width constraint.</p>

<p><img src="https://i.sstatic.net/lViki.png" alt="enter image description here"></p>

<p>Also, I found this article to be close to what I need:</p>

<ul>
<li><a href="http://www.emis.de/journals/ASUO/mathematics/pdf6/75_86_PIacob_DMarinescu_CLuca.pdf" rel="nofollow noreferrer">Covering with rectangular pieces</a> by Paul Iacob, Daniela Marinescu, and Cristina Luca</li>
</ul>

<p>Maybe a better question is "How can I identify rectangular-like portions of a concave polygon?"
<img src="https://i.sstatic.net/xGGEd.png" alt="enter image description here"></p>

<p>Here is an image showing the desired implementation:
<img src="https://i.sstatic.net/SDk9O.png" alt="enter image description here"></p>

<p>The green is the actual material usage. The red rectangles are the layouts. The blue is the MBR of the entire polygon. I am thinking I should try to get little MBRs and fill them in. The 2-3 green rectangles in the upper left corner that terminate into the middle of the polygon are expensive. That is what I want to minimize. The green rectangles have a min and max width and height, but I can use as many rows and columns necessary to cover a region. Again, I must minimize the number of rectangles that do not span across the input. I can also modify the shape of the green rectangle to fit in small places that is also very expensive. In other words, getting as many rectangles as possible to span as much as possible is ideal.</p>

CC BY-SA 3.0
2012-08-21T21:32:39.520Z
Looking at your examples, it seems like you want to minimize spill while simultaneously minimizing number of rectangles. Is this correct? If so, your question doesn't specify in what way spill should be minimized.
Josephine Moeller
CC BY-SA 3.0
2012-08-21T22:36:37.553Z
Can you define spill?
Josh C.
CC BY-SA 3.0
2012-08-22T01:50:59.993Z
Your title says convex polygons, but the question talks of concave polygons. Perhaps you need to make some corrections?
Ankur
CC BY-SA 3.0
2012-08-22T06:45:31.363Z
By spill I mean what's left over after you subtract the polygon from the rectangles.
Josephine Moeller
CC BY-SA 3.0
2012-08-22T13:33:19.660Z
@JohnMoeller, I am not sure how to answer that or even think about answering that. The problem is similar to laying carpet, but I can't use triangles to fill in angled spaces. The rectangle must pass the angled space just enough, and what spills out of the polygon is wasted. If you are willing to help me fix my language, I'll keep trying to get it right.
Josh C.
CC BY-SA 3.0
2012-08-22T13:49:34.533Z
@JoshC.: Is a solution with 3 rectangles *always* better than a solution with 4 rectangles, even if you have more waste?
Jukka Suomela
CC BY-SA 3.0
2012-08-22T14:00:43.080Z
@JukkaSuomela, in the first two pictures, the polygon is roughly the same size, and in the first picture, I could have run three rectangles vertically as I did in the second. However, this is less desirable. I think the trick has to do with the perimeters of the rectangles. Maybe what I am trying to do is minimize the amount of boundry of rectangle that is inside of the polygon, and maximize the amount of boundry that is collinear with the edges of the polygon. However, sometimes the rectangles must spill out of the polygon to cover it fully.
Josh C.
CC BY-SA 3.0
2012-08-22T20:20:49.960Z
@JoshC Personally, I'm having a lot of trouble parsing what you're saying for the constraints of your problem. So, which is more important, wasted rectangle area or number of rectangles? Both? What's the tradeoff? You have to answer this before you can proceed solving your problem.
Josephine Moeller
CC BY-SA 3.0
2012-08-22T20:54:13.757Z
@JohnMoeller, I understand. This is a problem where a human can identify the solution easily but stating the problem correctly is quite difficult. The problem is similar to laying carpet or wall paper and the actual problem is a structural/architectual one. I am trying to identify regions of rectangular layouts that later will be filled with another form of tesselation. Finding those rectangles and handling the non-rectangular regions is the problem. Let me know if I can explain more.
Josh C.
CC BY-SA 3.0
2012-08-22T21:01:34.637Z
I think we should approach this first as a modelling question: the goal is not to come up with an algorithm that solves a well-defined optimisation problem, but the goal is to define the optimisation problem.
Jukka Suomela
CC BY-SA 3.0
2012-08-22T21:03:37.847Z
@JoshC.: Perhaps it would be also helpful if you tried to tell us more about the real-world application. I gather from your description that, for example, cutting is fairly expensive — ideally, the rectangular pieces would require as little cutting as possible. Is this correct?
Jukka Suomela
CC BY-SA 3.0
2012-08-22T21:04:08.727Z
@JukkaSuomela +1 for modeling, absolutely.
Josephine Moeller
CC BY-SA 3.0
2012-08-22T21:06:56.570Z
Agree, framing this in real cost terms would probably help quite a bit. E.g., we have a roll of carpet, so material cost is related to length, but we also have labor cost associated with cutting the carpet. Is this a good example?
Josephine Moeller
CC BY-SA 3.0
2012-08-22T21:49:28.437Z
@JohnMoeller I've updated the post with another picture. Let me know if I need to explain anything else.
Josh C.
CC BY-SA 3.0
2012-08-22T21:52:22.067Z
@JoshC. Well, that's not what I meant. I'm not trying to be a jerk here, but can you answer the question that Jukka asked in the comments? More examples aren't really helpful at this point.
Josephine Moeller
CC BY-SA 3.0
2012-08-22T21:57:28.660Z
@JohnMoeller, I think I see what you mean. I don't think you are being a jerk btw. Real cost with an emphasis on real is what you are looking for. I thought my last picture and explanation would be enough. What if I said anything that does not meet the ideal layout incurs a penalty of 1. A non-rectangular shape and a rectangle that terminates within the bounds of the polygon are equally weighted. I need the layout with the lowest penalty. 0 is ideal. Does that help?
Josh C.
CC BY-SA 3.0
2012-08-22T22:05:04.887Z
@JukkaSuomela does my last paragraph and image in the post help define the optimization problem? Also, see my last comment in response to John Moeller. Does a simplified penalty system help define cost?
Josh C.
CC BY-SA 3.0
2012-08-23T18:40:28.267Z
@JukkaSuomela with my last approach of inscribing rectangles, fewer would always be better. Between two unique results that have the same number of rectangles, the result occupying the most area wins.
Josh C.
CC BY-SA 4.0
2023-03-20T06:22:55.097Z
Cross-posted: https://mathoverflow.net/q/105164/37212
D.W.
<co.combinatorics><cg.comp-geom>
Cover a Concave Polygon with a minimum number of rectangles
Josh C.
# Cover a Concave Polygon with a minimum number of rectangles

(Asked by: username_0 on 2012-08-21)

I am trying to cover a simple concave polygon with a minimum rectangles. My rectangles can be any length, but they have maximum widths, and the polygon will never have an acute angle.

I thought about trying to decompose my concave polygon into triangles that produce a set of minimumally overlapping rectangles minimally bounding each triangle and then merging those rectangles into larger ones. However, I don't think this will work for small notches in the edges of the polygon. The triangles created by the reflex vertices on those notches will create the wrong rectangles. I am looking for rectangles that will span/ignore notches.

I don't really know anything about computational geometry, so I'm not really sure on how to begin asking the question.

I found other posts that were similar, but not what I need:

* [split polygon into minimum amount of rectangles and triangles](https://mathoverflow.net/questions/28303/split-polygon-into-minimum-amount-of-rectangles-and-triangles)
* [Covering an arbitrary polygon with minimum number of squares](https://mathoverflow.net/questions/91279/covering-an-arbitrary-polygon-with-minimum-number-of-squares)
* [Find $k$ rectangles so that they cover the maximum number of points](https://stackoverflow.com/questions/3476778/find-k-rectangles-so-that-they-cover-the-maximum-number-of-points)
* [Algorithm for finding the fewest rectangles to cover a set of rectangles](https://stackoverflow.com/questions/5919298/algorithm-for-finding-the-fewest-rectangles-to-cover-a-set-of-rectangles)

Some examples: Black is the input. Red is the acceptable output.

![enter image description here](https://i.sstatic.net/0NDBF.png)

Another exmaple: The second output is prefered. However, generating both outputs and using another factor to determine preference is probably necessary and not the responsibility of this algorithm.

![enter image description here](https://i.sstatic.net/9qgeJ.png)

![enter image description here](https://i.sstatic.net/n02UR.png)

Polygons that mimic curves are extremely rare. In this scenario much of the area of the rectangles is wasted. However, this is acceptable because each rectangle obeys the max width constraint.

![enter image description here](https://i.sstatic.net/lViki.png)

Also, I found this article to be close to what I need:

* [Covering with rectangular pieces](http://www.emis.de/journals/ASUO/mathematics/pdf6/75_86_PIacob_DMarinescu_CLuca.pdf) by Paul Iacob, Daniela Marinescu, and Cristina Luca

Maybe a better question is "How can I identify rectangular-like portions of a concave polygon?"
![enter image description here](https://i.sstatic.net/xGGEd.png)

Here is an image showing the desired implementation:
![enter image description here](https://i.sstatic.net/SDk9O.png)

The green is the actual material usage. The red rectangles are the layouts. The blue is the MBR of the entire polygon. I am thinking I should try to get little MBRs and fill them in. The 2-3 green rectangles in the upper left corner that terminate into the middle of the polygon are expensive. That is what I want to minimize. The green rectangles have a min and max width and height, but I can use as many rows and columns necessary to cover a region. Again, I must minimize the number of rectangles that do not span across the input. I can also modify the shape of the green rectangle to fit in small places that is also very expensive. In other words, getting as many rectangles as possible to span as much as possible is ideal.

**Tags:** co.combinatorics, cg.comp-geom

> **Comments:**
> **username_1**: Looking at your examples, it seems like you want to minimize spill while simultaneously minimizing number of rectangles. Is this correct? If so, your question doesn't specify in what way spill should be minimized.  
> **username_0**: Can you define spill?  
> **username_2**: Your title says convex polygons, but the question talks of concave polygons. Perhaps you need to make some corrections?  
> **username_1**: By spill I mean what's left over after you subtract the polygon from the rectangles.  
> **username_0**: @JohnMoeller, I am not sure how to answer that or even think about answering that. The problem is similar to laying carpet, but I can't use triangles to fill in angled spaces. The rectangle must pass the angled space just enough, and what spills out of the polygon is wasted. If you are willing to help me fix my language, I'll keep trying to get it right.  
> **username_3**: @JoshC.: Is a solution with 3 rectangles *always* better than a solution with 4 rectangles, even if you have more waste?  
> **username_0**: @JukkaSuomela, in the first two pictures, the polygon is roughly the same size, and in the first picture, I could have run three rectangles vertically as I did in the second. However, this is less desirable. I think the trick has to do with the perimeters of the rectangles. Maybe what I am trying to do is minimize the amount of boundry of rectangle that is inside of the polygon, and maximize the amount of boundry that is collinear with the edges of the polygon. However, sometimes the rectangles must spill out of the polygon to cover it fully.  
> **username_1**: @JoshC Personally, I'm having a lot of trouble parsing what you're saying for the constraints of your problem. So, which is more important, wasted rectangle area or number of rectangles? Both? What's the tradeoff? You have to answer this before you can proceed solving your problem.  
> **username_0**: @JohnMoeller, I understand. This is a problem where a human can identify the solution easily but stating the problem correctly is quite difficult. The problem is similar to laying carpet or wall paper and the actual problem is a structural/architectual one. I am trying to identify regions of rectangular layouts that later will be filled with another form of tesselation. Finding those rectangles and handling the non-rectangular regions is the problem. Let me know if I can explain more.  
> **username_3**: I think we should approach this first as a modelling question: the goal is not to come up with an algorithm that solves a well-defined optimisation problem, but the goal is to define the optimisation problem.  
> **username_3**: @JoshC.: Perhaps it would be also helpful if you tried to tell us more about the real-world application. I gather from your description that, for example, cutting is fairly expensive — ideally, the rectangular pieces would require as little cutting as possible. Is this correct?  
> **username_1**: @JukkaSuomela +1 for modeling, absolutely.  
> **username_1**: Agree, framing this in real cost terms would probably help quite a bit. E.g., we have a roll of carpet, so material cost is related to length, but we also have labor cost associated with cutting the carpet. Is this a good example?  
> **username_0**: @JohnMoeller I've updated the post with another picture. Let me know if I need to explain anything else.  
> **username_1**: @JoshC. Well, that's not what I meant. I'm not trying to be a jerk here, but can you answer the question that Jukka asked in the comments? More examples aren't really helpful at this point.  
> **username_0**: @JohnMoeller, I think I see what you mean. I don't think you are being a jerk btw. Real cost with an emphasis on real is what you are looking for. I thought my last picture and explanation would be enough. What if I said anything that does not meet the ideal layout incurs a penalty of 1. A non-rectangular shape and a rectangle that terminates within the bounds of the polygon are equally weighted. I need the layout with the lowest penalty. 0 is ideal. Does that help?  
> **username_0**: @JukkaSuomela does my last paragraph and image in the post help define the optimization problem? Also, see my last comment in response to John Moeller. Does a simplified penalty system help define cost?  
> **username_0**: @JukkaSuomela with my last approach of inscribing rectangles, fewer would always be better. Between two unique results that have the same number of rectangles, the result occupying the most area wins.  
> **username_4**: Cross-posted: https://mathoverflow.net/q/105164/37212  

---

## 2 answers

### Answer by username_5 on 2012-12-01. Score: 3

This is a variant of geometric set cover. Depending on the exact settings, you might be able to do some good approximation. The problem is of course NP-Hard. The natural huersitics are to use greedy algorithm (always pick the rectangle/strip that covers the most area not covered yet. The alternative technique is to use reweighing. There are some interesting theoretical results, but frankly, nothing that should be too useful in practice. One interesting hueristic you might want to try, is to first decompose your polygon into minimal number of convex shapes (using Keil dynamic programming algorithm), and then covering each convex polygon separately...

> **Comments:**
> **username_0**: I'm not familiar with the Keil Dynamic Programming algorithm. However, I did find a method to work using a combination of the Largest-Inscribed Rectangle and Minimum-Bounding Rectangle algorithms with some variants based upon heuristics.  

---

### Answer by username_6 on 2012-08-23. Score: 2

I think [this paper](http://www.cs.helsinki.fi/u/polishch/pages/suit.pdf) may be of some help. Obviously it's not the same problem--in fact it's the reverse problem, covering a rectangle with polygons--but some of the ideas could be a starting point. In particular, this reverse problem is NP-hard and I suspect yours may be as well (though there's no obvious extension of the reduction as far as I can tell).

E. Arkin, A. Efrat, G. Hart, I. Kostitsyna, A. Kroller, J. Mitchell, and V. Polishchuk. Scandinavian Thins on Top of Cake: On the Smallest One-Size-Fits-All Box.
*Fun with Algorithms*. pg.16-27. 2012

> **Comments:**
> **username_0**: Thank you for your suggestion. I've been working with the engineering and manufacturing departments at my company to bring more clarificaiton to this problem. I am still waiting to confirm, but I am now thinking an algorithm that would return sets of largest inscribed rectangles would work. While it does not completely cover the shape, it would give preference to the orthognal regions while leaving the non-orthogonal regions to some heuristics. The only trick is to maxamize those orthogonal regions. See my last image with the 9 lamda-like figures.  

---

