Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
415653 | Computational Geometry | 2013 | 10 Pages |
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
S. Cabello, J.M. Díaz-Báñez, P. Pérez-Lantero,