A linear-time approximation scheme for minimum weight triangulation of convex polygons

DOI10.1007/PL00009216MaRDI QIDQ1393070zbMATH OpenOpenAlexFDO

Authors Christos Levcopoulos, Drago Krznaric

Publication date 2 August 1998

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/pl00009216

zbMATH Keywords

approximation schemesconvex polygons

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• On approximation behavior of the greedy triangulation for convex polygons
• A New Heuristic for Minimum Weight Triangulation
• New results for the minimum weight triangulation problem
• scientific article; zbMATH DE number 742947

Cited in

(13)

• On approximation behavior of the greedy triangulation for convex polygons
• An almost four-approximation algorithm for maximum weight triangulation
• Approximating the minimum triangulation of convex 3-polytopes with bounded degrees
• A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation
• Approximation for minimum triangulation of convex polyhedra
• Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound
• A New Heuristic for Minimum Weight Triangulation
• On a conjecture by Plaisted and Hong
• A New Lower Bound Technique and Its Application: Tight Lower Bound for a Polygon Triangulation Problem
• scientific article; zbMATH DE number 1496856 (Why is no real title available?)
• A quasi-polynomial time approximation scheme for minimum weight triangulation
• The drawability problem for minimum weight triangulations
• A linear time algorithm for max-min length triangulation of a convex polygon

This page was built for publication: A linear-time approximation scheme for minimum weight triangulation of convex polygons

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