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ᵈ)). The previous-best polynomial-time approximation (for constant d) was a classical n^ε approximation by Fox and Pach [SODA'11] that has recently been improved to a OPTε-approximation algorithm by Cslovjecsek, Pilipczuk and W{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].