O. Aichholzer, F. Aurenhammer, G. Rote, and Y.-F. Xu
The classical greedy triangulation (GT) of a set
of
points in the plane
is the triangulation obtained by starting with the empty set (of edges) and
at each step adding the shortest compatible edge between two of the points of
, where a compatible edge is defined to be an edge that crosses none of
the previously added edges. In this paper we use the greedy method as a
general concept to compute a triangulation of a planar point set. We use
either edges or triangles as basic objects. Furthermore we give different
variants to compute the weight of the objects, either in a static or dynamic
way, leading to a total of
different greedy triangulation algorithms.
We investigate these algorithms in their quality of approximating the MWT.
