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

AlgorithmConvex polygonApproximation schemeMaximum weight triangulation

Mathematics Subject Classification ID

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

Cited in

(6)

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