Label placement by maximum independent set in rectangles
| Author(s) : | Subhash Suri Marc Van Kreveld Pankaj K. Agarwal, |
| Publisher : | N/A |
| Publication Date : | 1998 |
| ISSN : | N/A |
| Abstract : | Motivated by the problem of labeling maps, we investigate the problem of computing a large non-intersecting subset in a set of n rectangles in the plane. Our results are as follows. In O(n log n) time, we can find an O(log n)-factor approximation of the maximum subset in a set of n arbitrary axis-parallel rectangles in the plane. If all rectangles have unit height, we can find a 2-approximation in O(n log n) time. Extending this result, we obtain a (1 + 1, |