Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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

Levcopoulos, Christos LU orcid and Lingas, Andrzej LU (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:
author
and
organization
publishing date
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
2025-10-14 09:42:56
@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}},
}