Approximating the Maximum Independent Set of Convex Polygons with a Bounded Number of Directions
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913231614771200 |
|---|---|
| author | Grandoni, Fabrizio Husić, Edin Mari, Mathieu Tinguely, Antoine |
| author_facet | Grandoni, Fabrizio Husić, Edin Mari, Mathieu Tinguely, Antoine |
| contents | In the maximum independent set of convex polygons problem, we are given a set of $n$ convex polygons in the plane with the objective of selecting a maximum cardinality subset of non-overlapping polygons. Here we study a special case of the problem where the edges of the polygons can take at most $d$ fixed directions. We present an $8d/3$-approximation algorithm for this problem running in time $O((nd)^{O(d4^d)})$. The previous-best polynomial-time approximation (for constant $d$) was a classical $n^\varepsilon$ approximation by Fox and Pach [SODA'11] that has recently been improved to a $OPT^{\varepsilon}$-approximation algorithm by Cslovjecsek, Pilipczuk and Węgrzycki [SODA '24], which also extends to an arbitrary set of convex polygons. Our result builds on, and generalizes the recent constant factor approximation algorithms for the maximum independent set of axis-parallel rectangles problem (which is a special case of our problem with $d=2$) by Mitchell [FOCS'21] and Gálvez, Khan, Mari, Mömke, Reddy, and Wiese [SODA'22]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_07666 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximating the Maximum Independent Set of Convex Polygons with a Bounded Number of Directions Grandoni, Fabrizio Husić, Edin Mari, Mathieu Tinguely, Antoine Computational Geometry Data Structures and Algorithms F.2.2 In the maximum independent set of convex polygons problem, we are given a set of $n$ convex polygons in the plane with the objective of selecting a maximum cardinality subset of non-overlapping polygons. Here we study a special case of the problem where the edges of the polygons can take at most $d$ fixed directions. We present an $8d/3$-approximation algorithm for this problem running in time $O((nd)^{O(d4^d)})$. The previous-best polynomial-time approximation (for constant $d$) was a classical $n^\varepsilon$ approximation by Fox and Pach [SODA'11] that has recently been improved to a $OPT^{\varepsilon}$-approximation algorithm by Cslovjecsek, Pilipczuk and Węgrzycki [SODA '24], which also extends to an arbitrary set of convex polygons. Our result builds on, and generalizes the recent constant factor approximation algorithms for the maximum independent set of axis-parallel rectangles problem (which is a special case of our problem with $d=2$) by Mitchell [FOCS'21] and Gálvez, Khan, Mari, Mömke, Reddy, and Wiese [SODA'22]. |
| title | Approximating the Maximum Independent Set of Convex Polygons with a Bounded Number of Directions |
| topic | Computational Geometry Data Structures and Algorithms F.2.2 |
| url | https://arxiv.org/abs/2402.07666 |