Computing Balanced Islands in Two Colored Point Sets in the Plane

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(n4) time algorithm that for a given α∈[0,[Formula presented]] finds a convex set containing exactly ⌈αr⌉ red points and exactly ⌈αb⌉ blue points of S. If ⌈αr⌉+⌈αb⌉ is not much larger than [Formula presented]n, we improve the running time to O(nlog⁡n). We also provide an O(n2log⁡n) time algorithm to find a convex set containing exactly ⌈[Formula presented]⌉ red points and exactly ⌈[Formula presented]⌉ blue points of S, and show that balanced islands with more points do not always exist. © 2018 Elsevier B.V.