Independent set of intersection graphs of convex objects in 2D

摘要

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 is an element of S if si boolean AND sj not equal 0. 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 R-2. Specifically, given (i) a set of n line segments in the plane with maximurn independent set of size alpha, we present algorithms that find an independent set of size at least (alpha/(2 log(2n/alpha))) (1/2) in time O(n(3)) and (alpha/(2 log(2n/alpha))) (1/4) in time O(n(4/3) log(c) n), (ii) a set of it convex objects with maximum independent set of size alpha, we present an algorithm that finds an independent set of size at least (a/(2 log(2n/a))) (1/3) in time O(n(3) + tau(S)), assuming that S can be preprocessed in time tau (S) to answer certain primitive operations on these convex sets, and (iii) a set of n rectangles with maximum independent set of size beta n, for beta <= 1, we present an algorithm that computes an independent set of size Omega(beta(2)n). All our-algorithms use the notion of partial orders that exploit the geometric structure of the convex objects. (c) 2006 Elsevier B.V. All rights reserved.