Approximating Maximum Independent Set for Rectangles in the Plane
Approximating Maximum Independent Set for Rectangles in the Plane
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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\log\log n)$</tex> . The results are based on a new form of recursive partitioning in the plane, in which faces …