Constant-Level Greedy Triangulations Approximate the MWT Well

Oswin Aichholzer (), Franz Aurenhammer (), Günter Rote () and Yin-Feng Xu ()
Additional contact information
Oswin Aichholzer: Graz University of Technology
Franz Aurenhammer: Graz University of Technology
Günter Rote: Graz University of Technology
Yin-Feng Xu: Xi'an Jiaotong University

Journal of Combinatorial Optimization, 1998, vol. 2, issue 4, No 5, 369 pages

Abstract: Abstract 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 |GT(S)| ≤ 3 · 2k + 1|MWT(S)|, where k is the number of levels and MWT(S) is the minimum-weight triangulation of S.

Keywords: greedy triangulation; minimum-weight triangulation (search for similar items in EconPapers)
Date: 1998
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1009776619164 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:2:y:1998:i:4:d:10.1023_a:1009776619164

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009776619164

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().