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.
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.
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.
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.