The minimum weight triangulation problem with few inner points

DOI10.1016/J.COMGEO.2005.11.006MaRDI QIDQ2495946zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 30 June 2006

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2005.11.006

zbMATH Keywords

computational complexitydynamic programmingexact algorithmfixed-parameter tractabilitygeometric optimizationgraphical examplesminimum weight triangulation problemparameterizationprogramming involving graphs

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Numerical mathematical programming methods (65K05) Complexity and performance of numerical algorithms (65Y20) Programming involving graphs or networks (90C35) Dynamic programming (90C39)

Recommendations

• Parameterized and Exact Computation
• A Fixed-Parameter Algorithm for the Minimum Weight Triangulation Problem Based on Small Graph Separators
• Polynomial-time instances of the minimum weight triangulation problem
• A quasi-polynomial time approximation scheme for minimum weight triangulation
• New results for the minimum weight triangulation problem

Cites work

• A lower bound for -skeleton belonging to minimum weight triangulations
• Algorithms and Data Structures
• Computing a subgraph of the minimum weight triangulation
• DIAMONDS ARE NOT A MINIMUM WEIGHT TRIANGULATION'S BEST FRIEND
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• Maximum weight triangulation and graph drawing
• Minimal Triangulations of Polygonal Domains
• On -skeleton as a subgraph of the minimum weight triangulation
• Polynomial-time instances of the minimum weight triangulation problem
• Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation
• The traveling salesman problem with few inner points

Cited in

(12)

• A fixed parameter algorithm for optimal convex partitions
• Polynomial-time instances of the minimum weight triangulation problem
• New results for the minimum weight triangulation problem
• A new asymmetric inclusion region for minimum weight triangulation
• Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound
• FIXED PARAMETER ALGORITHMS FOR THE MINIMUM WEIGHT TRIANGULATION PROBLEM
• A Fixed-Parameter Algorithm for the Minimum Weight Triangulation Problem Based on Small Graph Separators
• Parameterized and Exact Computation
• On a linear program for minimum-weight triangulation
• Minimum weight disk triangulations and fillings
• Algorithms and Computation
• The drawability problem for minimum weight triangulations

This page was built for publication: The minimum weight triangulation problem with few inner points

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