# Divide a polygon in minimum number of rectangles and triangles

• Jan 24th 2011, 11:10 AM
jainsapna14
Divide a polygon in minimum number of rectangles and triangles
Divide a polygon in minimum number of rectangles and triangles.

This problem is similar to that of triangulation.

Any polygon(irregular or regular) is to be divided into minimum number of rectangles and triangles.
• Jan 25th 2011, 04:44 PM
kylecronan

Do you really mean rectangles, or do you want to consider decompositions that use quadrilaterals with non-right angles? Hopefully not, because that seems harder.

One observation is that if we minimize triangles, with everything left being a rectangle, then we have minimized figures overall. Possibly the best way to do this would be to repeatedly remove ears that are not part of a chain of 3 segments at right angles. What's left should (maybe) be the maximal rectilinear subpolygon. There are algorithms known for minimal rectangulation of simple rectilinear polygons.
• Jan 25th 2011, 11:37 PM
jainsapna14
Thanks Kylecronan
Thanks kylecronan for reply. Polygons can be both concave and convex.
In this case how can we divide the polygon in minimum number of rectangles?
• Jan 26th 2011, 12:34 AM
kylecronan