split polygon into minimum amount of rectangles and triangles Hi
is there an algorithm which cuts a polygon into a minimum amount of preferably rectangles and where not possible (e.g. edges) into triangles?
 A: I'm not sure what you mean about the triangles, but if a polygon has all its sides axis-parallel, it is possible to find a partition into the minimum possible number of rectangles in polynomial time. The idea is to find the maximum number of disjoint axis-parallel diagonals that have two concave vertices as endpoints, split along those, and then form one more split for each remaining concave vertex. To find the maximum number of disjoint axis-parallel diagonals, form the intersection graph of the diagonals; this graph is bipartite so its maximum independent set can be found in polynomial time by graph matching techniques.
This method comes from several independent papers:


*

*W. Lipski, Jr., E. Lodi, F. Luccio, C. Mugnai, and L. Pagli. On two-dimensional data
organization II. Fundamenta Informaticae, 2:245–260, 1979.

*T. Ohtsuki. Minimum dissection of rectilinear regions. In Proc. IEEE Int. Symp. Circuits
and Systems, pages 1210–1213, 1982.

*L. Ferrari, P. V. Sankar, and J. Sklansky. Minimal rectangular partitions of digitized blobs.
Computer Vision, Graphics, and Image Processing, 28(1):58–71, 1984.


It's described in more detail in section 3 of my survey paper arXiv:0908.3916.
