Synthesizing data structure requirements from algorithm specifications : case studies from recursive subdivision for computer graphics and animation.

Abstract

Summary form only given. We propose that the data structure requirements of an algorithm may be synthesized from the algorithm specification. The evidence of that is drawn from observing that the flow of control of an algorithm is governed every step of the way by the information it gets from its data structure, which somehow should imply strong constraints on the way this data structure should be constructed. This in turn must have an impact on the global efficiency of the algorithm, since that is very much dependent on the ease with which such information can thus be obtained. This investigation is conducted through a couple of nontrivial algorithms in the area of recursive subdivision, a central area of research in computer-aided geometric design and computer graphics. The conclusions of this investigation are further verified through robust implementations of these algorithms with the supporting data structures drawn from this investigation.