page 1  (31 pages)
2to next section

GASP{II: A Geometric Algorithm Animation System for an

Electronic Classroom ?

Maria Shneerson and Ayellet Tal
Department of Applied Mathematics and Computer Science
The Weizmann Institute of Science
Rehovot, Israel, 76100


This paper describes GASP{II, an algorithm animation system for geometric computing. Because views of the same running algorithm may reside on different machines, GASP{II is particularly suitable for an electronic classroom. End-user may choose to use different views of the same running algorithm, allowing each student to study the algorithm in the most appropriate way. Moreover, end-users can run the animation in different speeds, and focus on the parts of the algorithm which they find difficult. Limiting the domain to computational geometry makes it possible to automate large parts of the process of creating an animation and the programmer can choose to be isolate from any concern about how graphics is done. Finally, GASP{II provides a visual debugging facility for geometric computing.

1 Introduction

Geometric algorithms can be highly complex and difficult to grasp. The ability to visually follow the construction and manipulation of geometric objects all the way, can greatly facilitate the understanding of an algorithm. An algorithm animation can expose properties of an algorithm that are otherwise hard to grasp, and help get some intuition into the way the algorithm operates. Unfortunately, there are few visualization tools available and even fewer which exploit the visual nature of geometric algorithms. The lack of visual tools makes it almost impossible for instructors to use animations in order to illustrate the studied algorithms.

The lack of adequate software tools is also one of the major reasons for the unusual slowness of the standard programming cycle. There are hardly any debugging tools available that make use of the visual nature of geometry. This is unfortunate since bugs in code which are usually difficult to track down from standard ASCII dumps of coordinates and parameters, can be easily spot by visualizing the graphical representations.

A well-designed algorithm animation system can provide the best solution both as an educational tool and a step towards a visual debugger. By restricting the focus of such a system to algorithms with a geometric flavor, it is possible to develop a compact system that is accessible to even naive users. In a well{defined domain, knowledge about the kinds of objects and the kinds of operations that need to be visualized can be used by the system. This is the main idea behind the development of GASP{II, the system presented in this paper.

?This work has been supported in part by the Israeli Ministry of Science, Eshkol Grant 0554-2-96.