| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1142482 | Operations Research Letters | 2011 | 6 Pages |
Abstract
Let S be a bicolored set of n points in the plane. A subset I of S is an island if there is a convex set C such that I=Câ©S. We give an O(n3)-time algorithm to compute a monochromatic island of maximum cardinality. Our approach is adapted to optimize similar (decomposable) objective functions. Finally, we use our algorithm to give an O(logn)-approximation for the problem of computing the minimum number of convex polygons that cover a class region.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
C. Bautista-Santiago, J.M. DÃaz-Báñez, D. Lara, P. Pérez-Lantero, J. Urrutia, I. Ventura,