Progress on maximum weight triangulation

DOI10.1016/J.COMGEO.2005.11.001MaRDI QIDQ2489534zbMATH OpenOpenAlexFDO

Authors Jianbo Qian, Cao An Wang

Publication date 28 April 2006

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2005.11.001

zbMATH Keywords

algorithmconstant approximationpolynomial-time 4.238-approximation

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Review text

Instead of the very hard minimum weight triangulation problem, the authors study the maximum weight triangulation and obtain a polynomial-time 4.238-approximation for the problem.

Cites work

• An efficient algorithm for determining the convex hull of a finite planar set
• scientific article; zbMATH DE number 3160756 (Why is no real title available?)
• scientific article; zbMATH DE number 871937 (Why is no real title available?)
• scientific article; zbMATH DE number 1446325 (Why is no real title available?)
• Maximum weight triangulation and graph drawing
• Minimal Triangulations of Polygonal Domains
• On approximation behavior of the greedy triangulation for convex polygons

Cited in

(2)

• A note on a QPTAS for maximum weight triangulation of planar point sets
• Further results on the Bruijn weight classes

This page was built for publication: Progress on maximum weight triangulation

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