# Approximating Maximum Independent Set for Rectangles in the Plane

arXiv: https://arxiv.org/abs/2101.00326 · HTML: https://mlsanity.com/paper/2101.00326/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jan 2021.

## Built on by (most cited first, 1 of 1)

- [Approximation Algorithms for ROUND-UFP and ROUND-SAP](https://mlsanity.com/paper/2202.03492/) (2022)

## Abstract (arXiv)

We give a polynomial-time constant-factor approximation algorithm for maximum independent set for (axis-aligned) rectangles in the plane. Using a polynomial-time algorithm, the best approximation factor previously known is O(loglog n). The results are based on a new form of recursive partitioning in the plane, in which faces that are constant-complexity and orthogonally convex are recursively partitioned into a constant number of such faces.