Decomposing Octilinear Polygons into Triangles and Rectangles

In this paper we study the minimal decomposition of octilinear polygons with holes into octilinear triangles and rectangles. This new problem is relevant in the context of modern electronic CAD systems, where it arises when the generation and propagation of electromagnetic noise into multi-layer PCBs has to be detected. It can be seen as a generalization of a problem deeply investigated in the last decades: the minimal decomposition of rectilinear polygons into rectangles, which is solvable in polynomial time. We show that the new problem is NP-hard. We also show the NP-hardness of a related problem, that is the decomposition of an octilinear polygon with holes into octilinear convex polygons. For both problems, we propose efficient approximation algorithms.