The minimum weight triangulation problem with few inner points

DOI10.1016/j.comgeo.2005.11.006zbMath1093.65016OpenAlexW2068541391MaRDI QIDQ2495946

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 programmingparameterizationgeometric optimizationexact algorithmfixed-parameter tractabilitygraphical examplesprogramming involving graphsminimum weight triangulation problem

Mathematics Subject Classification ID

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

Related Items (3)

A new asymmetric inclusion region for minimum weight triangulation ⋮ A fixed parameter algorithm for optimal convex partitions ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Polynomial-time instances of the minimum weight triangulation problem
• Computing a subgraph of the minimum weight triangulation
• Maximum weight triangulation and graph drawing
• The traveling salesman problem with few inner points
• Minimal Triangulations of Polygonal Domains
• Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation
• DIAMONDS ARE NOT A MINIMUM WEIGHT TRIANGULATION'S BEST FRIEND
• Algorithms and Data Structures
• A lower bound for \(\beta\)-skeleton belonging to minimum weight triangulations
• On \(\beta\)-skeleton as a subgraph of the minimum weight triangulation

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