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

Math @ Duke





.......................

.......................


Publications [#235489] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Mustafa, NH, Independent set of intersection graphs of convex objects in 2D, Computational Geometry, vol. 34 no. 2 (May, 2006), pp. 83-95, Elsevier BV, ISSN 0925-7721 [doi]
    (last updated on 2023/06/02)

    Abstract:
    The intersection graph of a set of geometric objects is defined as a graph G=(S,E) in which there is an edge between two nodes s i, s j∈S if s i∩s j≠ ∅. The problem of computing a maximum independent set in the intersection graph of a set of objects is known to be NP-complete for most cases in two and higher dimensions. We present approximation algorithms for computing a maximum independent set of intersection graphs of convex objects in ℝ 2. Specifically, given (i) a set of n line segments in the plane with maximum independent set of size α, we present algorithms that find an independent set of size at least (α/(2log(2n/α))) 1/2 in time O(n 3) and (α/(2log(2n/α))) 1/4 in time O(n 4/3log cn), (ii) a set of n convex objects with maximum independent set of size α, we present an algorithm that finds an independent set of size at least (α/(2log(2n/α))) 1/3 in time O(n 3+τ (S)), assuming that S can be preprocessed in time τ(S) to answer certain primitive operations on these convex sets, and (iii) a set of n rectangles with maximum independent set of size βn, for β≤1, we present an algorithm that computes an independent set of size Ω( β 2n) . All our algorithms use the notion of partial orders that exploit the geometric structure of the convex objects. © 2006 Elsevier 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 27708-0320