The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

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

På svenska

Author

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.

Department/s

  • Computer Science

Publishing year

2014

Language

English

Pages

414-416

Publication/Series

Information Processing Letters

Volume

114

Issue

8

Document type

Journal article

Publisher

Elsevier

Topic

  • Computer Science

Keywords

  • Approximation algorithms
  • Planar straight-line graph
  • Triangulation
  • Maximum weight triangulation
  • Time complexity
  • Quasi-polynomial time
  • approximation scheme

Status

Published

ISBN/ISSN/Other

  • ISSN: 0020-0190