JCSE, vol. 18, no. 3, pp.135-143, 2024

DOI: http://dx.doi.org/10.5626/JCSE.2024.18.3.135

Covering Points in the Plane by Two Rectangular Annuli

Sang Won Bae
Division of Artificial Intelligence and Computer Science, Kyonggi University, Suwon, Korea

Abstract: 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

Keyword: Annulus; Rectangular annulus; Geometric location; Computational geometry; Algorithm

Full Paper:   25 Downloads, 74 View