On two-dimensional data organization II¹

Article type: Research Article

Authors: Lipski Jr., Witold^a | Lodi, Elena^b | Luccio, Fabrizio^b | Mugnai, Cristina^b | Pagli, Linda^b

Affiliations: [a] Institute of Computer Science, Polish Academy of Sciences | [b] Istituto di Scienze dell’Informazione, Università di Pisa

Note: [1] This work has been supported in part by Consiglio Nazionale delle Ricerche of Italy, under grant No. 75.01035.01.

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.

Keywords: information storage and retrieval, bidimensional memory, figure description, minimal disjoint description, aligned edges, computational geometry

DOI: 10.3233/FI-1978-2116

Journal: Fundamenta Informaticae, vol. 2, no. 1, pp. 245-260, 1978