Independent set of intersection graphs of convex objects in 2D

Published

Journal Article

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 si, sj ∈ S if si ∩ sj ≠ ∅. 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 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 (i) (κ/2 log(2n/κ))1/2 in time O(n3) and (ii) (κ/2 log(2n/κ))1/4 in time O(n4/3 logc n). For 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 (κ/2 log(2n/κ))1/3 in time O(n3+τ(S)), assuming that S can be preprocessed in time τ(S) to answer certain primitive operations on these convex sets. © Springer-Verlag Berlin Heidelberg 2004.

Duke Authors

Cited Authors

  • Agarwal, PK; Mustafa, NH

Published Date

  • December 1, 2004

Published In

Volume / Issue

  • 3111 /

Start / End Page

  • 127 - 137

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

Citation Source

  • Scopus