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

DOI10.1016/0020-0190(86)90038-4zbMATH Open0584.68080OpenAlexW2111409442MaRDI QIDQ1069709FDOQ1069709

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

computational geometrygreedy algorithmVoronoi diagramminimum weight triangulationpoint distribution

Mathematics Subject Classification ID

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

Cites Work

• Parallel concepts in graph theory
• 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

Cited In (11)

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

This page was built for publication: The greedy and Delaunay triangulations are not bad in the average case

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