TIGHT LOWER BOUNDS FOR MINIMUM WEIGHT TRIANGULATION HEURISTICS

Authors
LEVCOPOULOS C KRZNARIC D
Citation
C. Levcopoulos et D. Krznaric, TIGHT LOWER BOUNDS FOR MINIMUM WEIGHT TRIANGULATION HEURISTICS, Information processing letters, 57(3), 1996, pp. 129-135
Citations number
14
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
57
Issue
3
Year of publication
1996
Pages
129 - 135
Database
ISI
SICI code
0020-0190(1996)57:3<129:TLBFMW>2.0.ZU;2-6
Abstract
The minimum spanning tree heuristic is obtained by optimally triangula ting a subgraph of the Delaunay triangulation, whereas the greedy span ning tree heuristic is obtained by optimally triangulating a subgraph of the greedy triangulation. In this paper it is shown that these two known heuristics can produce triangulations that are Omega(n), respect ively Omega(root n), times longer than the optimum, which are tight bo unds.