TY - GEN

T1 - Quasi-polynomial time approximation scheme for sparse subsets of polygons

AU - Har-Peled, Sariel

PY - 2014

Y1 - 2014

N2 - 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).

AB - 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).

KW - Approximation algorithms

KW - Independent set

KW - QPTAS

UR - http://www.scopus.com/inward/record.url?scp=84904438570&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84904438570&partnerID=8YFLogxK

U2 - 10.1145/2582112.2582157

DO - 10.1145/2582112.2582157

M3 - Conference contribution

AN - SCOPUS:84904438570

SN - 9781450325943

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 120

EP - 129

BT - Proceedings of the 30th Annual Symposium on Computational Geometry, SoCG 2014

PB - Association for Computing Machinery

T2 - 30th Annual Symposium on Computational Geometry, SoCG 2014

Y2 - 8 June 2014 through 11 June 2014

ER -