Minimum Decompositions of Polygonal Objects

This chapter discusses techniques for decompositions of objects into the minimum number of some component type. In many applications, the objects encountered are rectilinear polygons. In image processing, the boundaries of objects are often stored on a grid that usually implies that digitized images are rectilinear polygons. Very large-scale integration (VLSI) designs are also often stored on a grid and typically contain many rectilinear polygons. The chapter discusses the decompositions of rectilinear polygons when Steiner points are allowed and when Steiner points are disallowed. It also discusses the decomposition of arbitrary simple polygons when Steiner points are allowed and when Steiner points are disallowed. The result in this study concerns the partitioning of a polygonal region into a minimum number of trapezoids with two horizontal sides. Triangles with a horizontal side are considered to be trapezoids with two horizontal sides, one of which is degenerate. This problem is closely related to VLSI artwork data processing systems of electron-beam lithography for VLSI microfabrication. The chapter also discusses the decomposition of object which contains holes