**F. Aurenhammer and Y.-F.Xu**

A *triangulation* of a given set of points in the Euclidean plane
is a maximal set of non-crossing line segments spanned by . The problem of
automatically generating *optimal triangulations* for a point set has
been a subject of research since decades. As the number of different
triangulations of is an exponential function of , enumerating all
possible triangulations and selecting an optimal one (exhaustive search) is
too time-consuming even for small . In fact, constructing optimal
triangulations in polynomial time is a challenging task. Results on
optimizing *combinatorial* properties of triangulations, such as their
degree or connectivity, are rare. Most optimization criteria for which
efficient algorithms are known concern *geometric* properties of the
edges and triangles. The present survey article is devoted to this topic.