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

Summary, in English

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. (C) 2014 Elsevier B.V. All rights reserved.

• Författare: Christos Levcopoulos; Andrzej Lingas
• Avdelning/ar: Computer Science
• Publiceringsår: 2014
• Språk: Engelska
• Sidor: 414-416
• Publikation/Tidskrift/Serie: Information Processing Letters
• Volym: 114
• Issue: 8
• Länkar: http://dx.doi.org/10.1016/j.ipl.2014.03.002
• Dokumenttyp: Artikel i tidskrift
• Förlag: Elsevier
• Ämne: Computer Science
• Nyckelord: Approximation algorithms; Planar straight-line graph; Triangulation; Maximum weight triangulation; Time complexity; Quasi-polynomial time; approximation scheme
• Status: Published
• ISBN/ISSN/Övrigt: ISSN: 0020-0190