Back to Search
Start Over
SMALLEST COLOR-SPANNING OBJECT REVISITED.
- Source :
- International Journal of Computational Geometry & Applications; Oct2009, Vol. 19 Issue 5, p457-478, 22p, 7 Diagrams
- Publication Year :
- 2009
-
Abstract
- Given a set of n colored points in IR<superscript>2</superscript> 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(n<superscript>2</superscript>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))<superscript>2</superscript>log m) time. Our algorithm for identifying the smallest color-spanning rectangle of arbitrary orientation runs in O(n<superscript>3</superscript>log m) time and O(n) space. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 02181959
- Volume :
- 19
- Issue :
- 5
- Database :
- Complementary Index
- Journal :
- International Journal of Computational Geometry & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 44839971
- Full Text :
- https://doi.org/10.1142/S0218195909003076