A note on a QPTAS for maximum weight triangulation of planar point sets

作者：Levcopoulos Christos; Lingas Andrzej^*

来源：Information Processing Letters, 2014, 114(8): 414-416.

DOI：10.1016/j.ipl.2014.03.002

• Approximation algorithms
• Planar straight-line graph
• Triangulation
• Maximum weight triangulation
• Time complexity
• Quasi-polynomial time approximation scheme

We observe that the recent quasi-polynomial time approximation scheme (QPTAS) of Adamaszek and Wiese for the Maximum Weight Independent Set of Polygons problem, where polygons have at most a polylogarithmic number of vertices and nonnegative weights, yields:
1. a QPTAS for the problem of finding, for a set S of n points in the plane, a planar straight-line graph (PSLG) whose vertices are the points in S and whose each interior face is a simple polygon with at most a polylogarithmic in n number of vertices such that the total weight of the inner faces is maximized, and in particular,
2. a QPTAS for maximum weight triangulation of a planar point set.

• 出版日期2014-8