Label placement by maximum independent set in rectangles.
Pankaj K. Agarwal, Marc J. van Kreveld, Subhash Suri · 1997
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 + n 2k\\Gamma1 ) time, for any integer k 1. 1 Introduction Automated label placement is an important problem in geographic information systems (GIS), and has received considerable attention in recent years (for instance, see [6, 9]). The label placement problem includes positioning labels for area, line, and point features. The primary focus within the computational geometry community has been on labeling point features [5, 7, 17, 16]. A basic requirement in the label placement problem is that ...