Institution: | a Department of Computer Science, Box 90129, Duke University, Durham, NC 27708-0129, USA b Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508 TB, Utrecht, The Netherlands c Department of Computer Science, Washington University, St. Louis, MO 63130, USA |
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/k)-approximation in time O(n log n + n2k?1) time, for any integer k ≥ 1. |