Covering a bichromatic point set with two disjoint monochromatic disks

摘要

Let P be a set of n points in the plane in general position such that its elements are colored red or blue. We study the problem of finding two disjoint disks D ~r and D ~b such that D ~r covers only red points, D ~b covers only blue points, and the number of elements of P contained in D ~r∪D ~b is maximized. We prove that this problem can be solved in O(n11 ~(/3)polylogn) time. We also present a randomized algorithm that with high probability returns a (1-ε)- approximation to the optimal solution in O(n4 ~(/3)ε- ~6polylogn) time.