SMALLEST COLOR-SPANNING OBJECT REVISITED
Sandip Das, Partha P. Goswami, Subhas Chandra Nandy · International Journal of Computational Geometry & Applications · 2009
Given a set of n colored points in IR2 with a total of m (3 ≤ m ≤ n) colors, the problem of identifying the smallest color-spanning object of some predefined shape is studied in this paper. We shall consider two different shapes: (i) corridor and (ii) rectangle of arbitrary orientation. Our proposed algorithm for identifying the smallest color-spanning corridor is simple and runs in O(n2 log n) time using O(n) space. A dynamic version of the problem is also studied, where new points may be added, and the narrowest color-spanning corridor at any instance can be reported in O(mn(α(n))2 log m) time. Our algorithm for identifying the smallest color-spanning rectangle of arbitrary orientation runs in O(n3 log m) time and O(n) space.