New greedy triangulation algorithms

O. Aichholzer, F. Aurenhammer, G. Rote, and Y.-F. Xu


The classical greedy triangulation (GT) of a set $S$ of $n$ 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 $S$, 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 $156$ different greedy triangulation algorithms. We investigate these algorithms in their quality of approximating the MWT.

Reference: O. Aichholzer, F. Aurenhammer, G. Rote, and Y.-F. Xu. New greedy triangulation algorithms. In Proc. $12^{th}$ European Workshop on Computational Geometry CG '96, pages 11-14, Muenster, Germany, 1996.