Label placement by maximum independent set in rectangles

Journal Article (Journal Article)

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)-approximationin time O(n log n + n2k-1) time, for any integer k ≥ 1. © 1998 Elsevier Science B.V. All rights reserved.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Van Kreveld, M; Suri, S

Published Date

  • January 1, 1998

Published In

Volume / Issue

  • 11 / 3-4

Start / End Page

  • 209 - 218

International Standard Serial Number (ISSN)

  • 0925-7721

Digital Object Identifier (DOI)

  • 10.1016/S0925-7721(98)00028-5

Citation Source

  • Scopus