Oswin Aichholzer, Franz Aurenhammer, Günter Rote, and Yin-Feng Xu:

Constant-level greedy triangulations approximate the MWT well

  1. 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.
  2. Journal of Combinatorial Optimization 2 (1999), 361–369.

Abstract

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.

  PostScript file (gzipped)   pdf file
other papers about this subject
Last update: August 16, 2004.