TY  - JOUR
T1  - An Algorithm for Computing a Minimum-Width Color-Spanning Rectangular Annulus
AU  - Bae, Sang Won 
JO  - Journal of KIISE, JOK
PY  - 2017
DA  - 2017/1/14
DO  - 
KW  - color-spanning object
KW  - annulus
KW  - rectangle
KW  - covering problem
KW  - computational geometry
KW  - algorithm
AB  - 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.