<p>David Eppstein gave an excellent answer for this question <a href="https://mathoverflow.net/questions/28303/split-polygon-into-minimum-amount-of-rectangles-and-triangles">here on MathOverflow</a> (responding to a question for which it is not quite as good an answer). To summarize, there is a polynomial-time algorithm for finding the minimum number of rectangles.</p>

CC BY-SA 2.5
2011-01-21T04:37:20.003Z
2011-01-21T11:01:21.903Z
2017-04-13T12:57:54.777Z
Peter Shor 
<p>I imagine this must be an introductory computational geometry question, but I'm not sure of the best search phrases, and I'm interested in variations of the question, also, so I'm hoping for pointers to useful references. I'm interested in feasible algorithms for the following problem.</p>

<blockquote>
  <p>Input: A connected set of points (shape) in $\mathbb{Z} \times \mathbb{Z}$.<br>
  Output: A partition of the shape into rectangles, such that the rectangles do not overlap one another, and they cover only the shape, no "empty" space.</p>
</blockquote>

<p>I'm interested in finding the minimum number of rectangles, the "best" set of rectangles for any notion of best, whether this problem becomes easier or harder for different classes of shapes.</p>

<p>Thank you. :-)</p>

CC BY-SA 3.0
2012-08-21T20:42:43.107Z
@AaronSterling, do your rectangles need to be axis-parallel?
Josh C.
CC BY-SA 2.5
2011-01-20T02:13:11.283Z
Look at [this MathOverflow question](http://mathoverflow.net/questions/28303/split-polygon-into-minimum-amount-of-rectangles-and-triangles)
Peter Shor 
CC BY-SA 2.5
2011-01-20T02:35:24.363Z
@Peter Shor: Thanks very much.  That looks like exactly what I need.
Aaron Sterling
CC BY-SA 2.5
2011-01-20T04:12:07.500Z
So should this be an answer ? or should the question be closed ?
Suresh Venkat
CC BY-SA 2.5
2011-01-20T20:04:51.533Z
@Suresh: I think it resolves my question, though perhaps someone else might have something to add about variants of the problem.  I would prefer the question remain open in case anyone else has anything to add.  I would be happy to accept it as an answer if @Peter Shor posted it as such.
Aaron Sterling
CC BY-SA 2.5
2011-01-21T04:34:32.597Z
I guess I can post it as an answer, even though it seems like I did very little work. You should wait to accept it until you're sure nobody else has anything to add.
Peter Shor 
<reference-request><cg.comp-geom>
Partitioning a connected shape into rectangles
Aaron Sterling
# Partitioning a connected shape into rectangles

(Asked by: username_0 on 2011-01-20)

I imagine this must be an introductory computational geometry question, but I'm not sure of the best search phrases, and I'm interested in variations of the question, also, so I'm hoping for pointers to useful references. I'm interested in feasible algorithms for the following problem.

> Input: A connected set of points (shape) in $\mathbb{Z} \times \mathbb{Z}$.  
> Output: A partition of the shape into rectangles, such that the rectangles do not overlap one another, and they cover only the shape, no "empty" space.

I'm interested in finding the minimum number of rectangles, the "best" set of rectangles for any notion of best, whether this problem becomes easier or harder for different classes of shapes.

Thank you. :-)

**Tags:** reference-request, cg.comp-geom

> **Comments:**
> **username_2**: Look at [this MathOverflow question](http://mathoverflow.net/questions/28303/split-polygon-into-minimum-amount-of-rectangles-and-triangles)  
> **username_0**: @Peter Shor: Thanks very much.  That looks like exactly what I need.  
> **username_3**: So should this be an answer ? or should the question be closed ?  
> **username_0**: @Suresh: I think it resolves my question, though perhaps someone else might have something to add about variants of the problem.  I would prefer the question remain open in case anyone else has anything to add.  I would be happy to accept it as an answer if @username_2posted it as such.  
> **username_2**: I guess I can post it as an answer, even though it seems like I did very little work. You should wait to accept it until you're sure nobody else has anything to add.  
> **username_1**: @AaronSterling, do your rectangles need to be axis-parallel?  

---

## 1 answers

### Answer by username_2 on 2011-01-21. Score: 9 | Accepted answer

David Eppstein gave an excellent answer for this question [here on MathOverflow](https://mathoverflow.net/questions/28303/split-polygon-into-minimum-amount-of-rectangles-and-triangles) (responding to a question for which it is not quite as good an answer). To summarize, there is a polynomial-time algorithm for finding the minimum number of rectangles.


---

