Access Restriction

Author Chor, Benny ♦ Leiserson, Charles E. ♦ Rivest, Ronald L. ♦ Shearer, James B.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1986
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
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 $\textit{M}$ memory chips according to a “Fibonacci” lattice. The memory organization guarantees that, if a rectilinearly oriented rectangle contains fewer than $\textit{M}/$ @@@@5 pixels, then all pixels will reside in different memory chips and thus can be accessed simultaneously. Moreover, any $\textit{M}$ consecutive pixels, arranged either horizontally or vertically, can be accessed simultaneously.We also define a continuous analog 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?” We show the existence of such a set with density 1/ @@@@5, and prove this is optimal by giving a matching upper bound.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1986-01-02
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 33
Issue Number 1
Page Count 19
Starting Page 86
Ending Page 104

Open content in new tab

   Open content in new tab
Source: ACM Digital Library