Approximating the Maximum Independent Set of Convex Polygons with a Bounded Number of Directions
<|reference_start|>Approximating the Maximum Independent Set of Convex Polygons with a Bounded Number of Directions: 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\k{e}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\'{a}lvez, Khan, Mari, M\"{o}mke, Reddy, and Wiese [SODA'22].<|reference_end|>
@article{grandoni2024approximating,
    title={Approximating the Maximum Independent Set of Convex Polygons with a
  Bounded Number of Directions},
    author={Fabrizio Grandoni, Edin Husi'c, Mathieu Mari, Antoine Tinguely},
    journal={arXiv preprint arXiv:2402.07666},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.07666},
    primaryClass={cs.CG cs.DS}
}