Triangulations play an important role in approximation, CAGD, numerica
l analysis, and elsewhere. In this paper we are concerned with the pro
blem of constructing triangulations which are optimal in some sense. O
ur aim is to show how simulated annealing can be used to search for gl
obally optimal triangulations for a wide class of optimality criteria.
We also give several examples to illustrate its performance on a vari
ety of problems of interest in CAGD and surface fitting.