FIXED PARAMETER ALGORITHMS FOR THE MINIMUM WEIGHT TRIANGULATION PROBLEM

DOI10.1142/S0218195908002581MaRDI QIDQ3520429zbMATH OpenOpenAlexFDO

Authors Magdalene Grantson Borgelt, Christian Borgelt, Christos Levcopoulos

Publication date 26 August 2008

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0218195908002581

zbMATH Keywords

divide-and-conquer algorithmdynamic programmingfixed parameter algorithmminimum weight triangulationnumerical examplespolygon

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Numerical mathematical programming methods (65K05) Combinatorial optimization (90C27) Dynamic programming (90C39)

Recommendations

• Algorithms and Computation
• A Fixed-Parameter Algorithm for the Minimum Weight Triangulation Problem Based on Small Graph Separators
• Parameterized and Exact Computation
• The minimum weight triangulation problem with few inner points
• A fixed parameter algorithm for optimal convex partitions

Cites work

• A heuristic triangulation algorithm
• A lower bound for -skeleton belonging to minimum weight triangulations
• A New Heuristic for Minimum Weight Triangulation
• DIAMONDS ARE NOT A MINIMUM WEIGHT TRIANGULATION'S BEST FRIEND
• Finding a minimal cover for binary images: An optimal parallel algorithm
• scientific article; zbMATH DE number 3639144 (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 -skeleton as a subgraph of the minimum weight triangulation
• Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation
• The Boolean Basis Problem and How to Cover Some Polygons by Rectangles

Cited in

(4)

• A fixed parameter algorithm for optimal convex partitions
• A Fixed-Parameter Algorithm for the Minimum Weight Triangulation Problem Based on Small Graph Separators
• Solving large-scale minimum-weight triangulation instances to provable optimality
• On a linear program for minimum-weight triangulation

This page was built for publication: FIXED PARAMETER ALGORITHMS FOR THE MINIMUM WEIGHT TRIANGULATION PROBLEM

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