Interactive animation of ordered set algorithms using three-dimensional graphics.

Abstract

After reading the book Combinatorics and Partially Ordered Sets written by W. T. Trotter, we wondered how much more effective an interactive version of this book would be. Using hypertext linking techniques a reader would get immediate access not only to the referenced index entry point, but to all referred to or linked information. Such a system would become even more powerful if the algorithms were not only explained in words, but available as interactive animations which could be played with. Algorithm animation is a form of program visualization that includes a number of specialized subareas that will be addressed in this thesis: In the first part of the thesis, we will address the issue of data structure visualization, for instance, the structure of partially ordered sets (Posets). We will describe methods for visualizing Posets in 2D and then motivate the need and the importance of providing three-dimensional representation of these structures and discuss how 3D graphics can provide additional information to the structure, while maximizing readability and visibility through the use of computations and metrics. In the second part we will focus on the area of the algorithm animation. We will introduce our model for abstracting the data, the operations and the semantics of computer programs, and the creation of graphical views of those abstractions. We will then, explain what is an interactive mapping (operation mapping) and their relations with input data and the algorithms, and finally we will present our system's architecture and discuss its components. We emphasize that the potential of such algorithm animation environment is great, but can be fully realized only if they are sufficiently easy, highly interactive, and enjoyable to use. This dissertation is a step toward achieving these goals.