Independent set of intersection graphs of convex objects in 2D

AbstractThe 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 R2. 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(n3) and (α/(2log(2n/α)))1/4 in time O(n4/3logcn), (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(n3+τ(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