Home Bookmarks Papers Blog

Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons


Sariel Har-Peled.
Full journal version is here.
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 [AW13, AW14] to polygons of arbitrary complexity. 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., $K_{2,2}$).
PDF of conference version (but get the full version here).
Slide talks:
  1. KAIST talk, 6/2/2014.
  2. SoCG talk: black / white.

Last modified: Thu Jun 5 07:14:17 CDT 2014