Maximum independent set of rectangles

Parinya Chalermsook*, Julia Chuzhoy

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

80 Citations (Scopus)


We study the Maximum Independent Set of Rectangles (MISR) problem: given a collection R of n axis-parallel rectangles, find a maximum-cardinality subset of disjoint rectangles. MISR is a special case of the classical Maximum Independent Set problem, where the input is restricted to intersection graphs of axis-parallel rectangles. Due to its many applications, ranging from map labeling to data mining, MISR has received a significant amount of attention from various research communities. Since the problem is NP-hard, the main focus has been on the design of approximation algorithms. Several groups of researches have independently suggested O(log n)-approximation algorithms for MISR, and this remained the best currently known approximation factor for the problem. The main result of our paper is an O(log log n)-approximation algorithm for MISR. Our algorithm combines existing approaches for solving special cases of the problem, in which the input set of rectangles is restricted to containing specific intersection types, with new insights into the combinatorial structure of sets of intersecting rectangles in the plane. We also consider a generalization of MISR to higher dimensions, where rectangles are replaced by d-dimensional hyper-rectangles. Our results for MISR imply an O((log n) d-2 log log n)-approximation algorithm for this problem, improving upon the best previously known O((log n)d-1)-approximation.

Original languageEnglish
Title of host publicationProceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms
Number of pages10
Publication statusPublished - 2009
MoE publication typeA4 Article in a conference publication
EventACM-SIAM Symposium on Discrete Algorithms - New York, United States
Duration: 4 Jan 20096 Jan 2009
Conference number: 20


ConferenceACM-SIAM Symposium on Discrete Algorithms
Abbreviated titleSODA
Country/TerritoryUnited States
CityNew York


Dive into the research topics of 'Maximum independent set of rectangles'. Together they form a unique fingerprint.

Cite this