A New Heuristic for Minimum Weight Triangulation

DOI10.1137/0608053MaRDI QIDQ3801070zbMATH OpenOpenAlexFDO

Authors 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

almost certainlycomputational geometrydynamic programmingheuristicminimum spanning treeminimum weight triangulationplanar point setspolygonrunning timeuniform point distribution

Mathematics Subject Classification ID

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

Recommendations

• New results for the minimum weight triangulation problem
• Computing and Combinatorics
• A heuristic triangulation algorithm
• A linear-time approximation scheme for minimum weight triangulation of convex polygons
• scientific article; zbMATH DE number 742947

Cites work

• A note on Delaunay and optimal triangulations
• An efficient algorithm for determining the convex hull of a finite planar set
• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3651705 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• Minimal Triangulations of Polygonal Domains
• Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation
• On the average length of Delaunay triangulations
• The greedy and Delaunay triangulations are not bad in the average case

Cited in

(24)

• Computing a minimum weight triangulation of a sparse point set
• Computing a subgraph of the minimum weight triangulation
• New results for the minimum weight triangulation problem
• Drawing outerplanar minimum weight triangulations
• A linear-time approximation scheme for minimum weight triangulation of convex polygons
• LMT-skeleton heuristics for several new classes of optimal triangulations
• Improved heuristics for the minimum weight triangulation problem
• An almost four-approximation algorithm for maximum weight triangulation
• Minimum weight pseudo-triangulations
• Fast greedy triangulation algorithms.
• FIXED PARAMETER ALGORITHMS FOR THE MINIMUM WEIGHT TRIANGULATION PROBLEM
• A heuristic triangulation algorithm
• On a conjecture by Plaisted and Hong
• scientific article; zbMATH DE number 1308844 (Why is no real title available?)
• A grid-based approximation algorithm for the minimum weight triangulation problem
• Computing and Combinatorics
• scientific article; zbMATH DE number 742947 (Why is no real title available?)
• DIAMONDS ARE NOT A MINIMUM WEIGHT TRIANGULATION'S BEST FRIEND
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Algorithms and Computation
• A lower bound for -skeleton belonging to minimum weight triangulations
• On -skeleton as a subgraph of the minimum weight triangulation
• The drawability problem for minimum weight triangulations
• A new subgraph of minimum weight triangulations

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

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