F. Aurenhammer and Y.-F.Xu
of a given set
points in the plane is a
maximal set of non-crossing line segments spanned by
. The problem of
automatically generating optimal triangulations
for a point set
been a subject of research since decades. As the number of different
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
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.
Reference: F. Aurenhammer and Y.-F.Xu.
In P. C.A.Floudas, editor, Encyclopedia of Optimization, Second Edition,
pages 2757-2764. Springer, 2008.