Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation
From MaRDI portal
Publication:1256860
DOI10.1016/0020-0190(79)90104-2zbMath0404.68070OpenAlexW1964316024MaRDI QIDQ1256860
Albert L. Zobrist, Glenn K. Manacher
Publication date: 1979
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(79)90104-2
Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of packing and covering (05B40) Discrete mathematics in relation to computer science (68R99)
Related Items (21)
Computing a subgraph of the minimum weight triangulation ⋮ New results for the minimum weight triangulation problem ⋮ On approximation behavior of the greedy triangulation for convex polygons ⋮ Drawing outerplanar minimum weight triangulations ⋮ Good triangulations yield good tours ⋮ Improved heuristics for the minimum weight triangulation problem ⋮ Greedy triangulation can be efficiently implemented in the average case ⋮ A note on Delaunay and optimal triangulations ⋮ FIXED PARAMETER ALGORITHMS FOR THE MINIMUM WEIGHT TRIANGULATION PROBLEM ⋮ A New Heuristic for Minimum Weight Triangulation ⋮ Fast algorithms for greedy triangulation ⋮ On exclusion regions for optimal triangulations ⋮ Fast greedy triangulation algorithms. ⋮ Fast algorithms for greedy triangulation ⋮ The drawability problem for minimum weight triangulations ⋮ Simulated Annealing and Genetic Algorithms in Quest of Optimal Triangulations ⋮ On the average length of Delaunay triangulations ⋮ Toughness and Delaunay triangulations ⋮ Polynomial-time instances of the minimum weight triangulation problem ⋮ Approximating the minimum weight Steiner triangulation ⋮ The greedy and Delaunay triangulations are not bad in the average case
Cites Work
This page was built for publication: Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation
