<p>My problem:</p>

<ul>
<li><p>Dissect a grid polygon into rectangles. (A <em>grid polygon</em> is a <a href="http://en.wikipedia.org/wiki/Rectilinear_polygon" rel="nofollow">rectilinear polygon</a> all of whose vertices have integer coordinates.)</p></li>
<li><p>The rectangles must be taken from a predefined set (which includes a 1×1 rectangle, so the dissection is always possible).</p></li>
<li><p>Each rectangle has a cost which is not directly proportional to its size (a 2×3 rectangle may cost less 'per grid square covered' than a 1×1 rectangle).</p></li>
<li><p>No gaps or overlaps are allowed.</p></li>
<li><p>The optimal solution is the cheapest that covers the area.</p></li>
</ul>

<p>My first thoughts were to work out the cheapest 'per square covered' rectangle and fit as many of those into the area as possible, but it seems that might perform poorly if it means filling a lot of spaces with small, expensive pieces.</p>

<p>I realise this is likely NP-hard, so I am probably looking for a heuristic rather than an algorithm. It seems in some ways similar to a bin-packing problem or a knapsack problem, but I can't see how to extend the solutions to these problems. I may just be lacking the right terminology, so if anyone could point me in the right direction to get started, I'd be grateful.</p>

CC BY-SA 3.0
2012-03-16T10:26:34.463Z
It's normal to use the terms *dissection* when overlaps are forbidden (as in this case) and *cover* when overlaps are allowed. I changed the title accordingly.
Gareth Rees
CC BY-SA 3.0
2012-03-16T10:30:02.197Z
If the set of rectangles were unconstrained, and every rectangle had the same cost, then [this answer](http://stackoverflow.com/a/6634668/68063) would explain how to compute the cheapest dissection.
Gareth Rees
CC BY-SA 3.0
2012-03-25T11:18:04.873Z
@Kallikantzaros: This question could get good answers if it is asked on the new Computer Science SE site http://cs.stackexchange.com/. Can you try?
pad
<ds.algorithms><cg.comp-geom><heuristics>
Cheapest dissection of a grid polygon into rectangles with cost
Kallikantzaros
# Cheapest dissection of a grid polygon into rectangles with cost

(Asked by: username_0 on 2012-03-16)

My problem:

* Dissect a grid polygon into rectangles. (A *grid polygon* is a [rectilinear polygon](http://en.wikipedia.org/wiki/Rectilinear_polygon) all of whose vertices have integer coordinates.)
* The rectangles must be taken from a predefined set (which includes a 1×1 rectangle, so the dissection is always possible).
* Each rectangle has a cost which is not directly proportional to its size (a 2×3 rectangle may cost less 'per grid square covered' than a 1×1 rectangle).
* No gaps or overlaps are allowed.
* The optimal solution is the cheapest that covers the area.

My first thoughts were to work out the cheapest 'per square covered' rectangle and fit as many of those into the area as possible, but it seems that might perform poorly if it means filling a lot of spaces with small, expensive pieces.

I realise this is likely NP-hard, so I am probably looking for a heuristic rather than an algorithm. It seems in some ways similar to a bin-packing problem or a knapsack problem, but I can't see how to extend the solutions to these problems. I may just be lacking the right terminology, so if anyone could point me in the right direction to get started, I'd be grateful.

**Tags:** ds.algorithms, cg.comp-geom, heuristics
> **Comments:**
> **username_1**: It's normal to use the terms *dissection* when overlaps are forbidden (as in this case) and *cover* when overlaps are allowed. I changed the title accordingly.  
> **username_1**: If the set of rectangles were unconstrained, and every rectangle had the same cost, then [this answer](http://stackoverflow.com/a/6634668/68063) would explain how to compute the cheapest dissection.  
> **username_2**: @Kallikantzaros: This question could get good answers if it is asked on the new Computer Science SE site http://cs.stackexchange.com/. Can you try?  

---

## 0 answers

