Polynomial-time instances of the minimum weight triangulation problem

DOI10.1016/0925-7721(93)90016-YzbMath0799.68183MaRDI QIDQ1314524

Efthymios Anagnostou, Derek Gordon Corneil

Publication date: 3 March 1994

Published in: Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

complexityminimum weight triangulationpolynomial time algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (5)

Minimum convex partition of a constrained point set ⋮ A lower bound for \(\beta\)-skeleton belonging to minimum weight triangulations ⋮ The minimum weight triangulation problem with few inner points ⋮ Unnamed Item ⋮ Counting triangulations and other crossing-free structures via onion layers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The greedy and Delaunay triangulations are not bad in the average case
• A note on Delaunay and optimal triangulations
• The farthest point Delaunay triangulation minimizes angles
• Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation
• The concept of state in discrete dynamic programming
• Decomposing a Polygon into Simpler Components
• A heuristic triangulation algorithm
• Minimal Triangulations of Polygonal Domains
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• Hypersingular integrals in boundary element fracture analysis
• The NP-completeness column: An ongoing guide

This page was built for publication: Polynomial-time instances of the minimum weight triangulation problem