Approximating the Maximum Independent Set of Convex Polygons with a Bounded Number of Directions

Abstract

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(d{4}^d)})$. The previous-best polynomial-time approximation (for constant $d$) was a classical $n^{\epsilon }$ approximation by Fox and Pach [SODA'11] that has recently been improved to a $OP{T}^{\epsilon }$-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].

arXiv commentTo appear at SoCG 2024