Approximating Maximum Independent Set for Rectangles in the Plane

.We give a polynomial-time constant-factor approximation algorithm for the maximum independent set of (axis-aligned) rectangles problem in the plane. Using a polynomial-time algorithm, the best approximation factor previously known is \(O(log log 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.