A note on a QPTAS for maximum weight triangulation of planar point sets |
| |
Authors: | Christos Levcopoulos Andrzej Lingas |
| |
Affiliation: | Department of Computer Science, Lund University, 22100 Lund, Sweden |
| |
Abstract: | 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,
|
| |
Keywords: | Approximation algorithms Planar straight-line graph Triangulation Maximum weight triangulation Time complexity Quasi-polynomial time approximation scheme |
本文献已被 ScienceDirect 等数据库收录! |
|