### Abstract

Finding the maximum independent set in the intersection graph of n axis-parallel rectangles is NP-hard. We re-examine two known approximation results for this problem. For the case of rectangles of unit height, Agarwal, van Kreveld and Suri [Comput. Geom. Theory Appl. 11 (1998) 209-218] gave a (1+1/k)-factor algorithm with an O(nlogn+n^{2k-1}) time bound for any integer constant k≥1; we describe a similar algorithm running in only O(nlogn+nΔ^{k-1}) time, where Δ≤n denotes the maximum number of rectangles a point can be in. For the general case, Berman, DasGupta, Muthukrishnan and Ramaswami [J. Algorithms 41 (2001) 443-470] gave a ⌈log_{k}n⌉-factor algorithm with an O(n^{k+1}) time bound for any integer constant k≥2; we describe similar algorithms running in O(nlogn+nΔ^{k-2}) and n^{O(k/logk)} time.

Original language | English (US) |
---|---|

Pages (from-to) | 19-23 |

Number of pages | 5 |

Journal | Information Processing Letters |

Volume | 89 |

Issue number | 1 |

DOIs | |

State | Published - Jan 16 2004 |

Externally published | Yes |

### Keywords

- Approximation algorithms
- Computational geometry
- Dynamic programming

### ASJC Scopus subject areas

- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications