Computing balanced islands in two colored point sets in the plane

Abstract Let S be a set of n points in general position in the plane, r of which are red and b of which are blue. In this paper we present algorithms to find convex sets containing a balanced number of red and blue points. We provide an O ( n 4 ) time algorithm that for a given α ∈ [ 0 , 1 2 ] finds a convex set containing exactly ⌈ α r ⌉ red points and exactly ⌈ α b ⌉ blue points of S . If ⌈ α r ⌉ + ⌈ α b ⌉ is not much larger than 1 3 n , we improve the running time to O ( n log ⁡ n ) . We also provide an O ( n 2 log ⁡ n ) time algorithm to find a convex set containing exactly ⌈ r + 1 2 ⌉ red points and exactly ⌈ b + 1 2 ⌉ blue points of S , and show that balanced islands with more points do not always exist.