Approximating Maximum Independent Set for Rectangles in the Plane

01/01/2021

∙

by   Joseph S. B. Mitchell, et al.

∙

0

∙

share

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 in a constant number of such faces.