Quasi-polynomial time approximation scheme for sparse subsets of polygons

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We describe how to approximate, in quasi-polynomial time, the largest independent set of polygons, in a given set of polygons. Our algorithm works by extending the result of Adamaszek and Wiese [1, 2] to polygons of arbitrary com-plexity. Surprisingly, the algorithm also works for computing the largest subset of the given set of polygons that has some sparsity condition. For example, we show that one can approximate the largest subset of polygons, such that the intersection graph of the subset does not contain a cycle of length 4 (i.e., K2,2).

Original languageEnglish (US)
Title of host publicationProceedings of the 30th Annual Symposium on Computational Geometry, SoCG 2014
PublisherAssociation for Computing Machinery
Pages120-129
Number of pages10
ISBN (Print)9781450325943
DOIs
StatePublished - Jan 1 2014
Event30th Annual Symposium on Computational Geometry, SoCG 2014 - Kyoto, Japan
Duration: Jun 8 2014Jun 11 2014

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other30th Annual Symposium on Computational Geometry, SoCG 2014
CountryJapan
CityKyoto
Period6/8/146/11/14

Keywords

  • Approximation algorithms
  • Independent set
  • QPTAS

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Quasi-polynomial time approximation scheme for sparse subsets of polygons'. Together they form a unique fingerprint.

  • Cite this

    Har-Peled, S. (2014). Quasi-polynomial time approximation scheme for sparse subsets of polygons. In Proceedings of the 30th Annual Symposium on Computational Geometry, SoCG 2014 (pp. 120-129). (Proceedings of the Annual Symposium on Computational Geometry). Association for Computing Machinery. https://doi.org/10.1145/2582112.2582157