Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation

DOI10.1016/0020-0190(79)90104-2MaRDI QIDQ1256860zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

computational complexitytriangulation of a planar point set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99) Combinatorial aspects of packing and covering (05B40)

Cited in

(21)

• A New Heuristic for Minimum Weight Triangulation
• On approximation behavior of the greedy triangulation for convex polygons
• On exclusion regions for optimal triangulations
• Fast algorithms for greedy triangulation
• A note on Delaunay and optimal triangulations
• Fast algorithms for greedy triangulation
• Approximating the minimum weight Steiner triangulation
• On the average length of Delaunay triangulations
• Toughness and Delaunay triangulations
• Improved heuristics for the minimum weight triangulation problem
• Polynomial-time instances of the minimum weight triangulation problem
• Computing a subgraph of the minimum weight triangulation
• Drawing outerplanar minimum weight triangulations
• Good triangulations yield good tours
• The greedy and Delaunay triangulations are not bad in the average case
• Simulated Annealing and Genetic Algorithms in Quest of Optimal Triangulations
• New results for the minimum weight triangulation problem
• The drawability problem for minimum weight triangulations
• FIXED PARAMETER ALGORITHMS FOR THE MINIMUM WEIGHT TRIANGULATION PROBLEM
• Greedy triangulation can be efficiently implemented in the average case
• Fast greedy triangulation algorithms.

This page was built for publication: Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1256860)