Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235411] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Kreveld, MV; Suri, S, Label placement by maximum independent set in rectangles, Computational Geometry: Theory and Applications, vol. 11 no. 3-4 (1998), pp. 209-218
    (last updated on 2017/12/17)

    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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320