Polynomial-time instances of the minimum weight triangulation problem

DOI10.1016/0925-7721(93)90016-YMaRDI QIDQ1314524zbMATH OpenFDO

Authors Efthymios Anagnostou, Derek G. Corneil

Publication date 3 March 1994

Published in Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

complexitypolynomial time algorithmminimum weight triangulation

Mathematics Subject Classification ID

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

Recommendations

• New results for the minimum weight triangulation problem
• Parameterized and Exact Computation
• The minimum weight triangulation problem with few inner points
• A quasi-polynomial time approximation scheme for minimum weight triangulation

Cites work

• scientific article; zbMATH DE number 432801 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 742947 (Why is no real title available?)
• A heuristic triangulation algorithm
• A note on Delaunay and optimal triangulations
• Decomposing a Polygon into Simpler Components
• Hypersingular integrals in boundary element fracture analysis
• Minimal Triangulations of Polygonal Domains
• Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• The NP-completeness column: An ongoing guide
• The concept of state in discrete dynamic programming
• The farthest point Delaunay triangulation minimizes angles
• The greedy and Delaunay triangulations are not bad in the average case

Cited in

(18)

• DIAMONDS ARE NOT A MINIMUM WEIGHT TRIANGULATION'S BEST FRIEND
• Finding a maximum weight triangle in n ^3-Δ time, with applications
• Minimum weight triangulation is NP-hard
• A new subgraph of minimum weight triangulations
• Minimum weight pseudo-triangulations
• On a linear program for minimum-weight triangulation
• On a linear program for minimum-weight triangulation
• Minimum convex partition of a constrained point set
• Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound
• Solving large-scale minimum-weight triangulation instances to provable optimality
• A quasi-polynomial time approximation scheme for minimum weight triangulation
• Minimum-weight triangulation is NP-hard
• A lower bound for \(\beta\)-skeleton belonging to minimum weight triangulations
• Parameterized and Exact Computation
• The minimum weight triangulation problem with few inner points
• The drawability problem for minimum weight triangulations
• New results for the minimum weight triangulation problem
• Counting triangulations and other crossing-free structures via onion layers

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

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