Optimal triangulations

F. Aurenhammer and Y.-F.Xu

Abstract:

A triangulation of a given set $S$ of $n$ points in the plane is a maximal set of non-crossing line segments spanned by $S$. The problem of automatically generating optimal triangulations for a point set $S$ has been a subject of research since decades. As the number of different triangulations of $S$ is an exponential function of $n$, enumerating all possible triangulations and selecting an optimal one (exhaustive search) is too time-consuming even for small $n$. 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.

Reference: F. Aurenhammer and Y.-F.Xu. Optimal triangulations. In P. C.A.Floudas, editor, Encyclopedia of Optimization, Second Edition, pages 2757-2764. Springer, 2008.