Covering Points in the Plane by Two Rectangular Annuli

Given a set P of n points in the plane, we study the problem of covering P by an optimal pair of two disjoint rectangular annuli. The optimality is determined by a prescribed cost function that depends on the widths of the resulting rectangular annuli, such as the maximum or the sum of the widths of the two annuli. In this paper, we present the first O(n log n)-time algorithms for a wide range of cost functions, including the min-max and min-sum versions of the problem. We also show the matching lower bound of Ω(n log n), in particular, for the min-sum problem.