This web page contains the abstract of my paper:
"An Application of Number Theory to the Organization of Raster- Graphics Memory" with B. Chor, C.E. Leiserson and R.L. Rivest, J.ACM, 33(1986), p. 86-104.
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/(sqrt(5)) pixels, then all pixels will reside in different memory chips and thus can be accessed simultaneously. Moreover, any M consecutive pixels, arranged either horizontally or vertically, can be accessed simultaneously.
We also define a continous 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 ordered rectangle of unit area?" We show the existence of such a set with density 1/(sqrt(5)), and prove that this is optimal by giving a matching upper bound.
IBM Research home page |
James B. Shearer's home page |
[ IBM home page | Order | Search | Contact IBM | Help | (C) | (TM) ]