# 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