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

DOI10.1016/0020-0190(86)90038-4MaRDI QIDQ1069709zbMATH OpenOpenAlexFDO

Authors 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

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

Cited in

(11)

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

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)