On two-dimensional data organization II 1

Abstract

Following a previous Part I, two-dimensional sequential data organization is considered. A set of data is a figure on the storage. The elementary figure is the rectangle, and any figure is described by a set of rectangles. The decomposition of a figure into disjoint rectangles is studied. Some properties of the description composed of the minimum number of disjoint rectangles (MDD) are presented. It is shown that aligned edges of a figure play a fundamental role in the form of an MDD, and an algorithm is presented which constructs an MDD of an arbitrary figure in polynomial time.