Constant-level greedy triangulations approximate the MWT well
O. Aichholzer, F. Aurenhammer, G. Rote, and Y.-F. Xu
The well-known greedy triangulation
of a finite point set
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
that does not rely on the length ordering of the edges. Rather, it provides a
into levels, and the number of levels allows us to
bound the total edge length of
. In particular, we show
is the number of levels and
the minimum-weight triangulation of
Reference: O. Aichholzer, F. Aurenhammer, G. Rote, and Y.-F. Xu.
Constant-level greedy triangulations approximate the MWT well.
In C. Du, Zhang, editor, Proc. Int'l. Symp. Operations Research
& Applications ISORA'96, Lecture Notes in Operations Research, volume 2,
pages 309-318, Guilin, P. R. China, 1996. World Publishing Corporation.