decompose rectilinear polygons into rectangles with minimum internal borders I have a number of rectangles as shown in the attached diagram (labelled original) and I want to merge them together in a way (labelled Result ) to get the minimum internal borders. The reason I want to do this is because the rectangles will be converted to electromagnetic structures (I am writing an antenna simulator) and the execution complexity is minimized when the internal borders are a minimum. The original data is described by a list of rectangles. 
I am not very familiar with this class of mathematics so any help or ideas will be appreciated.
Original and Final polygon shapes
 A: It is an interesting problem. Here are a few thoughts though not a solution.
1) It might be conceptually easier to think of the goal as to minimize the combined perimeters of all the constituent rectangles. This is the length of the outer border plus twice the length of the internal borders. 
2) The original could be thought of as a region bounded by segments parallel to the axes rather than a given union of rectangles. I'll assume that you don't want holes in the interior although that might not change anything. Then drawing dividing lines horizontally and vertically from every corner gives a division into small  basic rectangles. It seems obvious that an optimal solution to your problem involves merging some of these basic rectangles into bigger rectangles, although I did not try to prove this.
3) I've taken your original region and done this finest division on the left. There are $10$ small rectangles and, if I count correctly, a total of $10+12+5+3+1=32$ rectangles where the summands record how many there are made of $1,2,3,4$ or $6$ basic rectangles.
4) On the right is what seems the best division to me. The thicker line near the top left could be switched for a vertical line from the same internal point, but that looks to be a little under $10\%$ longer.
5) In general one has an exact cover problem. Imagine a $34 \times 10$ $0,1$-matrix with each column recording which basic rectangles make up a possible solution rectangle. Each column has an associated weight which is the perimeter of that rectangle. One might run through all possible choices of columns which add to the all $1$'s vector. Then find the one with the least total weight.
There are fast algorithms for this problem. 
6) Furthermore, the linked algorithm builds a solution one rectangle at a time. As soon as a partial solution has weight greater than the minimal weight so far found, one can abandon it and all refinements. So one might start with the two solutions using all only the horizontal (or only the vertical) internal lines. There are ways to prioritize the columns so the ones with the most basic rectangles are considered first.
7) Perhaps one can show that only rectangles sharing part of the external border need be considered. The rectangles with an $*$ in them seem to me to be such that any solution using one of them can be improved
Other formulations are possible too.

