@Article{CLRS86,
  author = 	 { Benny Chor and Charles E. Leiseron and Ronald L. Rivest and James B. Shearer },
  title = 	 { An application of number theory to the organization of raster-graphics memory },
  acm =          { 712521 },
  journal = 	 { JACM },
  issn =         { 0004-5411 },
  OPTyear = 	 { 1986 },
  OPTmonth = 	 { January },
  date =         { 1986-01 },                  
  volume = 	 { 33 },
  number = 	 { 1 },
  pages = 	 { 86--104 },
  url =          { http://doi.acm.org/10.1145/4904.4800 },
  doi =          { 10.1145/4904.4800 },
  acmid =        { 4800 },
  publisher =    { ACM },
  keywords =     { {BITBLT}, Fibonacci lattices, golden ratio, interleaving, memory organization,
                   raster graphics, rectangles },                  
  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, and $M$ consecutive pixels arranged either horizontally
        or vertically, can be accessed simultaneously.
        \par
        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/\sqrt{5}$, and prove this is optimal by giving a matching upper bound.
                 },
}