@article{M772647F0,
title = "An Algorithm for Computing a Minimum-Width Color-Spanning Rectangular Annulus",
journal = "Journal of KIISE, JOK",
year = "2017",
issn = "2383-630X",
doi = "",
author = "Sang Won Bae",
keywords = "color-spanning object,annulus,rectangle,covering problem,computational geometry,algorithm",
abstract = "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."
}