Math @ Duke

Publications [#235411] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Kreveld, MV; Suri, S, Label placement by maximum independent set in rectangles,
Computational Geometry: Theory and Applications, vol. 11 no. 34
(1998),
pp. 209218
(last updated on 2018/03/17)
Abstract: Motivated by the problem of labeling maps, we investigate the problem of computing a large nonintersecting 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 axisparallel rectangles in the plane. If all rectangles have unit height, we can find a 2approximation in O(n log n) time. Extending this result, we obtain a (1 + 1/k)approximationin time O(n log n + n2k1) time, for any integer k ≥ 1. © 1998 Elsevier Science B.V. All rights reserved.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

