Faster approximation for maximum independent set on unit disk graph

Maximum independent set from a given set D of unit disks intersecting a horizontal line can be solved in O(n2) time and O(n2) space. As a corollary, we design a factor 2 approximation algorithm for the maximum independent set problem on unit disk graph which takes both time and space of O(n2). The best known factor 2 approximation algorithm for this problem runs in O(n2log⁡n) time and takes O(n2) space [1,2].