Accession Number : ADA140638
Title : An Application of Number Theory to the Organization of Raster-Graphics Memory.
Descriptive Note : Interim research rept.,
Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE
Personal Author(s) : Chor,B ; Leiserson,C ; Rivest,R ; Shearer,J
PDF Url : ADA140638
Report Date : Apr 1984
Pagination or Media Count : 24
Abstract : A high-resolution raster-graphics display is usually combined with processing power and a memory organization that facilitates basic graphics operations. For many applications, including interactive text processing, the ability to quickly move or copy small rectangles of pixels is essential. This paper proposes a novel organization of raster-graphics memory that permits all small rectangles to be moved efficiently. The memory organization is based on a doubly periodic assignment of pixels to M memory chips according to a Fibonacci lattice. The memory organization guarantees that if a rectilinearly oriented rectangle contains fewer than M/square root of 5 pixels, then all pixels will reside in different memory chips, and thus can be accessed simultaneously. The authors also define a continuous analogue of the problem which can be posed as, 'What is the maximum density of a set of points in the plane such that no two points are contained in the interior of a rectilinearly oriented rectangle of unit area.' They show the existence of such a set with density 1/square root of 5, and prove this is optimal by giving a matching upper bound.
Descriptors : *Number theory, *Computer graphics, *Memory devices, Rasters, High resolution, Chips(Electronics), Mathematical analysis, Text processing, Interactions, Square roots
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE