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

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11697/132090
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 1
social impact