Article ID Journal Published Year Pages File Type
415653 Computational Geometry 2013 10 Pages PDF
Abstract

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 DrDr and DbDb such that DrDr covers only red points, DbDb covers only blue points, and the number of elements of P   contained in Dr∪DbDr∪Db is maximized. We prove that this problem can be solved in O(n11/3polylogn) time. We also present a randomized algorithm that with high probability returns a (1−ε)(1−ε)-approximation to the optimal solution in O(n4/3ε−6polylogn) time.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,