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.

Decomposing Octilinear Polygons into Triangles and Rectangles

CICERONE, SERAFINO;DI STEFANO, GABRIELE
2013-01-01

Abstract

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.
978-3-319-13286-0
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: https://hdl.handle.net/11697/43446
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact