# Return to Question

3 Added picture of an actual structure, Each yellow rectangle (in the last diagram) will have an extension added to it.

I have a set of touching rectangles (Initial problem), and an associated graph relating the rectangles through the edges. I want to reduce the rectangles through graph operations to the minimum internal border (Optimal solution). Sub optimal solutions which can be solved quickly are also acceptable. The reason why the minimum internal border is needed because than the internal borders are discretized for Electromagnetic analysis. The fewer the internal borders the quicker the Electromagnetic analysis. Real world problems for analysis are much harder as shown at the end of the question.

The best method I have thought of is traversing the graph with each vertex having a cost (the width of the touching borders). If two vertices have the same width they can be absorbed into a single rectangle and hence a new vertex created. However I am interested in global optimum result or a result near the global optimum. I thought dynamic programming as solution and starting off from 1 there are two possible steps which yield a different global solution one which is optimal and the other solutions may be sub optimal or do not yield much improvement.

Am I on the right track using dynamic programming or is there some other algorithms or techniques which I may use. Thanks a lot for any help and ideas

I will go over the algorithm, however the final structure still consisting of rectlinear rectangles has a more complex representation as shown below. I think it will still work.

Example of a Real World problem I have a set of touching rectangles (Initial problem), and an associated graph relating the rectangles through the edges. I want to reduce the rectangles through graph operations to the minimum internal border (Optimal solution). Sub optimal solutions which can be solved quickly are also acceptable. The reason why the minimum internal border is needed because than the internal borders are discretized for Electromagnetic analysis. The fewer the internal borders the quicker the Electromagnetic analysis. Real world problems for analysis are much harder as shown at the end of the question.

The best method I have thought of is traversing the graph with each vertex having a cost (the width of the touching borders). If two vertices have the same width they can be absorbed into a single rectangle and hence a new vertex created. However I am interested in global optimum result or a result near the global optimum. I thought dynamic programming as solution and starting off from 1 there are two possible steps which yield a different global solution one which is optimal and the other solutions may be sub optimal or do not yield much improvement.

Am I on the right track using dynamic programming or is there some other algorithms or techniques which I may use. Thanks a lot for any help and ideas

I will go over the algorithm, however the final structure still consisting of rectlinear rectangles has a more complex representation as shown below. I think it will still work. Example of a Real World problem I have a set of touching rectangles (Initial problem), and an associated graph relating the rectangles through the edges. I want to reduce the rectangles through graph operations to the minimum internal border (Optimal solution). Sub optimal solutions which can be solved quickly are also acceptable. The reason why the minimum internal border is needed because than the internal borders are discretized for Electromagnetic analysis. The fewer the internal borders the quicker the Electromagnetic analysis. Real world problems for analysis are much harder as shown at the end of the question.

The best method I have thought of is traversing the graph with each vertex having a cost (the width of the touching borders). If two vertices have the same width they can be absorbed into a single rectangle and hence a new vertex created. However I am interested in global optimum result or a result near the global optimum. I thought dynamic programming as solution and starting off from 1 there are two possible steps which yield a different global solution one which is optimal and the other solutions may be sub optimal or do not yield much improvement.

Am I on the right track using dynamic programming or is there some other algorithms or techniques which I may use. Thanks a lot for any help and ideas

I will go over the algorithm, however the final structure still consisting of rectlinear rectangles has a more complex representation as shown below. I think it will still work. Example of a Real World problem 2 Post picture of a an actual structure

I have a set of touching rectangles (Initial problem), and an associated graph relating the rectangles through the edges. I want to reduce the rectangles through graph operations to the minimum internal border (Optimal solution). Sub optimal solutions which can be solved quickly are also acceptable. The reason why the minimum internal border is needed because than the internal borders are discretized for Electromagnetic analysis. The fewer the internal borders the quicker the Electromagnetic analysis. Real world problems for analysis are much harder as shown at the end of the question.

The best method I have thought of is traversing the graph with each vertex having a cost (the width of the touching borders). If two vertices have the same width they can be absorbed into a single rectangle and hence a new vertex created. However I am interested in global optimum result or a result near the global optimum. I thought dynamic programming as solution and starting off from 1 there are two possible steps which yield a different global solution one which is optimal and the other solutions may be sub optimal or do not yield much improvement.

Am I on the right track using dynamic programming or is there some other algorithms or techniques which I may use. Thanks a lot for any help and ideas

I will go over the algorithm, however the final structure still consisting of rectlinear rectangles has a more complex representation as shown below. I think it will still work. Example of a Real World problem I have a set of touching rectangles (Initial problem), and an associated graph relating the rectangles through the edges. I want to reduce the rectangles through graph operations to the minimum internal border (Optimal solution). Sub optimal solutions which can be solved quickly are also acceptable. The reason why the minimum internal border is needed because than the internal borders are discretized for Electromagnetic analysis. The fewer the internal borders the quicker the Electromagnetic analysis. Real world problems for analysis are much harder as shown at the end of the question.

The best method I have thought of is traversing the graph with each vertex having a cost (the width of the touching borders). If two vertices have the same width they can be absorbed into a single rectangle and hence a new vertex created. However I am interested in global optimum result or a result near the global optimum. I thought dynamic programming as solution and starting off from 1 there are two possible steps which yield a different global solution one which is optimal and the other solutions may be sub optimal or do not yield much improvement.

Am I on the right track using dynamic programming or is there some other algorithms or techniques which I may use. Thanks a lot for any help and ideas Example of a Real World problem I have a set of touching rectangles (Initial problem), and an associated graph relating the rectangles through the edges. I want to reduce the rectangles through graph operations to the minimum internal border (Optimal solution). Sub optimal solutions which can be solved quickly are also acceptable. The reason why the minimum internal border is needed because than the internal borders are discretized for Electromagnetic analysis. The fewer the internal borders the quicker the Electromagnetic analysis. Real world problems for analysis are much harder as shown at the end of the question.

The best method I have thought of is traversing the graph with each vertex having a cost (the width of the touching borders). If two vertices have the same width they can be absorbed into a single rectangle and hence a new vertex created. However I am interested in global optimum result or a result near the global optimum. I thought dynamic programming as solution and starting off from 1 there are two possible steps which yield a different global solution one which is optimal and the other solutions may be sub optimal or do not yield much improvement.

Am I on the right track using dynamic programming or is there some other algorithms or techniques which I may use. Thanks a lot for any help and ideas

I will go over the algorithm, however the final structure still consisting of rectlinear rectangles has a more complex representation as shown below. I think it will still work. Example of a Real World problem 1

# Reduce the total internal border of a set of touching rectangles (using graphs)

I have a set of touching rectangles (Initial problem), and an associated graph relating the rectangles through the edges. I want to reduce the rectangles through graph operations to the minimum internal border (Optimal solution). Sub optimal solutions which can be solved quickly are also acceptable. The reason why the minimum internal border is needed because than the internal borders are discretized for Electromagnetic analysis. The fewer the internal borders the quicker the Electromagnetic analysis. Real world problems for analysis are much harder as shown at the end of the question.

The best method I have thought of is traversing the graph with each vertex having a cost (the width of the touching borders). If two vertices have the same width they can be absorbed into a single rectangle and hence a new vertex created. However I am interested in global optimum result or a result near the global optimum. I thought dynamic programming as solution and starting off from 1 there are two possible steps which yield a different global solution one which is optimal and the other solutions may be sub optimal or do not yield much improvement.

Am I on the right track using dynamic programming or is there some other algorithms or techniques which I may use. Thanks a lot for any help and ideas Example of a Real World problem 