Oswin Aichholzer, Franz Aurenhammer, Günter Rote, and Yin-Feng Xu:
Constant-level greedy triangulations approximate the MWT well
- In: Proceedings of the Second International Symposium on Operations Research
and its Applications (ISORA'96), Guilin, China, December 11–13, 1996. Editors:
Ding-Zhu Du, Xiang-Sun Zhang, and Kan Cheng. Lecture Notes in Operations
Research 2, World Publishing Corporation, Beijing 1996, pp. 309–318.
- Journal of Combinatorial Optimization 2 (1999),
The well-known greedy triangulation of a finite point set is obtained by
looking at the edges in order of increasing length and inserting an edge if
it does not cross previously inserted ones. Exploiting the concept of
so-called light edges, we introduce a new way of defining the greedy
triangulation. It does not rely on the length ordering of the edges. It
decomposes the greedy triangulation into levels, and the number k of levels
allows us to bound the total edge length by
3·2k+1 times the minimum-weight
triangulation of the point set.
Last update: August 16, 2004.