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

DOI10.1007/S00453-004-1101-6MaRDI QIDQ1762986zbMATH OpenOpenAlexFDO

Authors Jianbo Qian, Cao An Wang

Publication date 11 February 2005

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-004-1101-6

zbMATH Keywords

AlgorithmApproximation schemeConvex polygonMaximum weight triangulation

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Polyhedral manifolds (52B70) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cited in

(6)

• On approximation behavior of the greedy triangulation for convex polygons
• A linear time approximation scheme for computing geometric maximum \(k\)-star
• An almost four-approximation algorithm for maximum weight triangulation
• Finding a maximum weight triangle in n ^3-Δ time, with applications
• Linear algorithm to find the largest intriangles of a planar convex polygon
• 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 maximum weight triangulation of convex polygons

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