“An Area Organized Data Structure for Interactive Graphics” by Jarvis

  • ©John F. Jarvis




    An Area Organized Data Structure for Interactive Graphics

Session/Category Title: Large Systems Session




    A problem common to many applications of interactive graphics is the response time of the system to a user input. This response time increases in severity as the quantity of data being manipulated increases. Programs for the design of integrated circuit masks are good examples of graphics systems where large quantities of data are processed. This response time problem is particularly severe for the windowing operation and other algorithms that must iteratively search the graphical data base.

    The problem addressed by this paper is the handling of large quantities of geometric data within the constraints of fast response times and minimal computer facilities. By large we mean designs requiring more than 20,000 coordinate pairs or equivalently 10,000 rectangles for their description. Desirable response times are 1 to 2 seconds for windowing operations and less than 1 second for geometrically localized modifications to the data base. Minimal computer facilities encompass the currently available 16 bit minicomputers equipped with a maximum of 32K words of fast memory and a moving head disc system.


    1. J. F. Jarvis, “The Design of Interactive Graphics Aids to Mask Layout,” Proc. IEEE, Vol. 60, pp. 35–39, January 1972.
    2. R. Williams, “A Survey of Data Structure for Computer Graphics Systems,” Computing Surveys, Vol. 3, pp. 1–22, March 1971.
    3. P. J. Denning, “Virtual Memory,” Computing Surveys, Vol. 2, pp. 153–190, September 1970.
    4. D. M. Ritchie and K. Thompson, “The UNIX Time Sharing System,” CACM, Vol. 17, pp. 1365–1375, July 1974.
    5. J. F. Jarvis, “A Graphical Display System Utilizing Plasma Panels,” presented at First Annual Conference on Computer Graphics, Boulder, Colorado, July 15, 1974.

ACM Digital Library Publication: