Decomposing Octilinear Polygons into Triangles and Rectangles - Discrete and Computational Geometry and Graphs - page 18

Decomposing Octilinear Polygons
into Triangles and Rectangles

B

Serafino Cicerone (

) and Gabriele Di Stefano

Dipartimento di Ingegneria e Scienze dell'Informazione e Matematica,
Universita degli Studi dell'Aquila, L'Aquila, Italy
{ serafino.cicerone,gabriele.distefano } @univaq.it

Abstract. In this paper we study the minimal decomposition of octilin-
ear 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 decompo-
sition of an octilinear polygon with holes into octilinear convex polygons.
For both problems, we propose ecient approximation algorithms.

· ·

Keywords: Polygon decomposition Octilinear polygons Approxima-

·

tion algorithms CAD applications

1 Introduction

The problems of partitioning a planar polygon into simpler components are well
studied in computational geometry, as they have various applications in com-
puter graphics, mesh generation, pattern recognition, VLSI, and more. Particular
examples of these problems are the decomposition of polygons into convex com-
ponents, triangles, or other exotic shapes like spiral, star-shaped, and monotone
components. (e.g., see [ 10 ] and references therein).
A specific problem concerns the partition into a minimum number of rec-
tangles of a rectilinear polygon, that is a polygon having the edges parallel
to two orthogonal directions [ 16 ]. Despite its specificity, rectangular partition
have many applications in VLSI, DNA micro-array design, processing and com-
pression of bitmap images [ 2 , 7 ]. The rectilinear polygon decomposition problem
has been solved in polynomial-time at earlier stage; for instance, we can find a

Work supported by the Research Grant 2012C4E3KT “PRIN 2012” Amanda (Algo-
rithmics for MAssive and Networked DAta) from the Italian Ministry of University
and Research.