The greedy and Delaunay triangulations are not bad in the average case

DOI10.1016/0020-0190(86)90038-4zbMath0584.68080OpenAlexW2111409442MaRDI QIDQ1069709

Andrzej Lingas

Publication date: 1986

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(86)90038-4

zbMATH Keywords

greedy algorithmminimum weight triangulationVoronoi diagramcomputational geometrypoint distribution

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Related Items

Drawing outerplanar minimum weight triangulations ⋮ Algorithms for minimum length partitions of polygons ⋮ Good triangulations yield good tours ⋮ Improved heuristics for the minimum weight triangulation problem ⋮ Greedy triangulation can be efficiently implemented in the average case ⋮ A New Heuristic for Minimum Weight Triangulation ⋮ Computing the minimum weight triangulation of a set of linearly ordered points ⋮ Fast greedy triangulation algorithms. ⋮ An O(n log n) plane-sweep algorithm for \(L_ 1\) and \(L_{\infty}\) Delaunay triangulations ⋮ Toughness and Delaunay triangulations ⋮ Polynomial-time instances of the minimum weight triangulation problem

Cites Work

• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• A note on Delaunay and optimal triangulations
• Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation
• Parallel concepts in graph theory