Approximation Algorithms for Maximum Independent Set of Pseudo-Disks

Research output: Contribution to journalArticlepeer-review


We present approximation algorithms for maximum independent set of pseudo-disks in the plane, both in the weighted and unweighted cases. For the unweighted case, we prove that a local-search algorithm yields a PTAS. For the weighted case, we suggest a novel rounding scheme based on an LP relaxation of the problem, which leads to a constant-factor approximation. Most previous algorithms for maximum independent set (in geometric settings) relied on packing arguments that are not applicable in this case. As such, the analysis of both algorithms requires some new combinatorial ideas, which we believe to be of independent interest.

Original languageEnglish (US)
Pages (from-to)373-392
Number of pages20
JournalDiscrete and Computational Geometry
Issue number2
StatePublished - Sep 2012


  • Approximation algorithms
  • Fréchet distance
  • Realistic input models

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Approximation Algorithms for Maximum Independent Set of Pseudo-Disks'. Together they form a unique fingerprint.

Cite this