Approximation algorithms for decomposing octilinear polygons

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 the generation and propagation of electromagnetic noise into multi-layer PCBs has to be detected. It is a generalization of a problem deeply investigated: the minimal decomposition of rectilinear polygons into rectangles. 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.

Authors

• Serafino Cicerone
• Gabriele Di Stefano

Keywords

• Computational geometry
• Polygon decomposition
• Octilinear polygons
• Approximation algorithms
• CAD applications