GENERATING RECTANGLES USING TWO-DIMENSIONAL GRAMMARS WITH TIME AND SPACE COMPLEXITY ANALYSES

摘要

A two-dimensional grammar for generating all possible rectangles is presented and illustrated by examples. The time and space complexity analyses of this grammar together with a parallel context-free array grammar and a free grammar are also presented. Generating pictures using two-dimensional grammars appear to be a fertile field for further study. The study of two-dimensional grammars has useful applications in region filling. pattern recognition. robotics, pictorial information system design and related areas.