1. SMALLEST COLOR-SPANNING OBJECT REVISITED.
- Author
-
Das, Sandip, Goswami, Partha P., and Nandy, Subhas C.
- Subjects
- *
ALGORITHMS , *COMPLEXITY (Philosophy) , *DUALITY theory (Mathematics) , *PERIMETERS (Geometry) , *SET theory - Abstract
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(n2log 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))2log m) time. Our algorithm for identifying the smallest color-spanning rectangle of arbitrary orientation runs in O(n3log m) time and O(n) space. [ABSTRACT FROM AUTHOR]
- Published
- 2009
- Full Text
- View/download PDF