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(log n)‐approximation for the problem of computing the minimum number of convex polygons that cover a class region.
