Computing optimal islands

Let S be a bicolored set of n points in the plane. A subset I of S is an island if there is a convex set C such that I=C∩S. We give an O(n3)-time algorithm to compute a monochromatic island of maximum cardinality. Our approach is adapted to optimize similar (decomposable) objective functions. Finally, we use our algorithm to give an O(logn)-approximation for the problem of computing the minimum number of convex polygons that cover a class region.