Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of
Polygons
Sariel Har-Peled.
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.
Slide talks: