A note on a QPTAS for maximum weight triangulation of planar point sets
(2014) In Information Processing Letters 114(8). p.414-416- 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, 2. a QPTAS for maximum weight triangulation of a planar point set. (C) 2014 Elsevier B.V. All rights reserved.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/4552370
- author
- Levcopoulos, Christos
LU
and Lingas, Andrzej LU
- organization
- publishing date
- 2014
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Approximation algorithms, Planar straight-line graph, Triangulation, Maximum weight triangulation, Time complexity, Quasi-polynomial time, approximation scheme
- in
- Information Processing Letters
- volume
- 114
- issue
- 8
- pages
- 414 - 416
- publisher
- Elsevier
- external identifiers
-
- wos:000336699200005
- scopus:84899933387
- ISSN
- 0020-0190
- DOI
- 10.1016/j.ipl.2014.03.002
- language
- English
- LU publication?
- yes
- id
- a6594232-3a7d-425a-b580-5e49bcfaf6e4 (old id 4552370)
- date added to LUP
- 2016-04-01 13:39:14
- date last changed
- 2022-01-27 20:20:37
@article{a6594232-3a7d-425a-b580-5e49bcfaf6e4, 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, 2. a QPTAS for maximum weight triangulation of a planar point set. (C) 2014 Elsevier B.V. All rights reserved.}}, author = {{Levcopoulos, Christos and Lingas, Andrzej}}, issn = {{0020-0190}}, keywords = {{Approximation algorithms; Planar straight-line graph; Triangulation; Maximum weight triangulation; Time complexity; Quasi-polynomial time; approximation scheme}}, language = {{eng}}, number = {{8}}, pages = {{414--416}}, publisher = {{Elsevier}}, series = {{Information Processing Letters}}, title = {{A note on a QPTAS for maximum weight triangulation of planar point sets}}, url = {{http://dx.doi.org/10.1016/j.ipl.2014.03.002}}, doi = {{10.1016/j.ipl.2014.03.002}}, volume = {{114}}, year = {{2014}}, }