A New Heuristic for Minimum Weight Triangulation

DOI10.1137/0608053zbMath0654.68050OpenAlexW2083525325MaRDI QIDQ3801070

Andrzej Lingas

Publication date: 1987

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0608053

zbMATH Keywords

dynamic programmingpolygonminimum weight triangulationheuristiccomputational geometryminimum spanning treeplanar point setsrunning timealmost certainlyuniform point distribution

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Convex sets in (2) dimensions (including convex curves) (52A10)

Related Items (10)

Computing a subgraph of the minimum weight triangulation ⋮ New results for the minimum weight triangulation problem ⋮ Drawing outerplanar minimum weight triangulations ⋮ Improved heuristics for the minimum weight triangulation problem ⋮ FIXED PARAMETER ALGORITHMS FOR THE MINIMUM WEIGHT TRIANGULATION PROBLEM ⋮ Fast greedy triangulation algorithms. ⋮ A lower bound for \(\beta\)-skeleton belonging to minimum weight triangulations ⋮ An almost four-approximation algorithm for maximum weight triangulation ⋮ On \(\beta\)-skeleton as a subgraph of the minimum weight triangulation ⋮ The drawability problem for minimum weight triangulations

Cites Work

• On the average length of Delaunay triangulations
• The greedy and Delaunay triangulations are not bad in the average case
• A note on Delaunay and optimal triangulations
• Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation
• An efficient algorithm for determining the convex hull of a finite planar set
• Minimal Triangulations of Polygonal Domains
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A New Heuristic for Minimum Weight Triangulation