### 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., K_{2,2}).

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 30th Annual Symposium on Computational Geometry, SoCG 2014 |

Publisher | Association for Computing Machinery |

Pages | 120-129 |

Number of pages | 10 |

ISBN (Print) | 9781450325943 |

DOIs | |

State | Published - Jan 1 2014 |

Event | 30th Annual Symposium on Computational Geometry, SoCG 2014 - Kyoto, Japan Duration: Jun 8 2014 → Jun 11 2014 |

### Publication series

Name | Proceedings of the Annual Symposium on Computational Geometry |
---|

### Other

Other | 30th Annual Symposium on Computational Geometry, SoCG 2014 |
---|---|

Country | Japan |

City | Kyoto |

Period | 6/8/14 → 6/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