Sang Won Bae

color-spanning object annulus RECTANGLE covering problem Computational geometry algorithm

In this paper, we present an algorithm that computes a minimum-width color spanning axis-parallel rectangular annulus. A rectangular annulus is a closed region between a rectangle and its offset, and it is thus bounded by two rectangles called its outer and inner rectangles. The width of a rectangular annulus is determined by the distance between its outer and inner rectangles. Given n points in the plane each of which has one of the prescribed k colors, we call a rectangular annulus color spanning if it contains at least one point for each of the k colors. Prior to this work, there was no known exact algorithm that computes a minimum-width color-spanning rectangular annulus. Our algorithm is the first to solve this problem and it runs efficiently in O(n-k)³nlogn) time.