Approximating Maximum Independent Set for Rectangles in the Plane
- Resource Type
- Working Paper
- Authors
- Mitchell, Joseph S. B.
- Source
- Subject
- Computer Science - Computational Geometry
Computer Science - Data Structures and Algorithms
- Language
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(\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.