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.
Approximation algorithms for decomposing octilinear polygons
Cicerone, Serafino
;Di Stefano, Gabriele
2019-01-01
Abstract
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.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.