Overview

The aim of this chapter is to introduce a variety of data structures and to show how they can be used profitably in a mesh generation context. To this end, some basic as well as more sophisticated data structures are recalled together with some algorithms of greater or lesser complexity. The discussion is then developed by means of various application examples related to situations extensively used in a meshing context.

While people having a computer science background may be familiar with these basic notions, we would nevertheless like to address this topic here in order to allow people less directly concerned to gain some knowledge of this (vast) topic, notably applied mathematicians or numericians. Moreover, in the mesh generation context, specific applications and uses of the classical data structures lead to specific situations and merit some comments.

The literature about data structures and algorithms is quite abundant. Among the usual references, the textbooks would include [Aho et al. 1983], [Wirth-1986], [Sedgewick-1988], [Cormen et al. 1990], [Samet-1990] and [Gonnet et al. 1991] as well as the unchallengeable [Knuth-1998a], not to mention many others that can also be consulted.

The complexity of an algorithm, both in terms of the number of operations and of the memory resource allocated, is analyzed from a theoretical point of view. However, we will show that specific theoretical results obtained in ad-hoc academic situations must be slightly nuanced. Indeed, numerous assumptions like "the points must be in general position" in a triangulation...