首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号