Covering Point Sets with Two Convex Objects
José Miguel Díaz-Báñez, Carlos Seara, J. Antoni Sellarès, Jorge Urrutia, Inmaculada Ventura · 2005
Let P2n be a point set in the plane with n red and n blue points. Let CR and CB (SR and SB) respectively be red and blue colored and disjoint disks (axisparallel squares). In this paper we prove the following results. Finding the positions for CR and CB that maximizes the number of red points covered by CR plus the number of blue points covered by CB can be done in O(n 3 log n) time. Finding two axis-parallel unit-squares with disjoint interiors that maximizes the sum of the red points covered by SR plus the number of blue points covered by SB can be done in O(n²) time.