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.

- January 24th 2011, 11:10 AMjainsapna14Divide 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. - January 25th 2011, 04:44 PMkylecronan
I can't answer your question, but I can maybe help you define it better. Are we just considering simple polygons? Convex?

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. - January 25th 2011, 11:37 PMjainsapna14Thanks 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? - January 26th 2011, 12:34 AMkylecronan
Okay, what about using quadrilaterals? Now that I think about it, it might be easier in this case because you could start with what is known about triangulation (combining adjacent triangles makes a quadrilateral).

It is a difficult problem! If you really need to know the answer you should talk to a computational geometer.