Constant-level greedy triangulations approximate the MWT well

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


The well-known greedy triangulation $GT(S)$ of a finite point set $S$ is obtained by inserting compatible edges in increasing length order, where an edge is compatible if it does not cross previously inserted ones. Exploiting the concept of so-called light edges, we introduce a definition of $GT(S)$ that does not rely on the length ordering of the edges. Rather, it provides a decomposition of $GT(S)$ into levels, and the number of levels allows us to bound the total edge length of $GT(S)$. In particular, we show $\vert GT(S)\vert \leq
3 \cdot 2^{k+1} \vert MWT(S)\vert$, where $k$ is the number of levels and $MWT(S)$ is the minimum-weight triangulation of $S$.

Reference: O. Aichholzer, F. Aurenhammer, G. Rote, and Y.-F. Xu. Constant-level greedy triangulations approximate the MWT well. Journal of Combinatorial Optimization, 2:361-369, 1999. [SFB-Report F003-050, TU Graz, Austria, 1995].