Approximation algorithms for decomposing octilinear polygons (Q2420578)

The problem of minimal decomposition of octilinear polygons with holes into octilinear triangles and rectangles is important in the generation and propagation of electromagnetic noise into multilayer PCBs, used in CAD systems. This problem is a generalization of the minimal decomposition of rectilinear polygons into rectangles which can be solved in polynomial time. In this paper the generalized problem is studied. It is also shown that this problem is NP-hard. Additionally, it is shown that a similar problem -- the decomposition of an octilinear polygon with holes into octinilear convex polygons -- is NP-hard as well. As a practical solution related to these problems, two approximation algorithms are proposed.