@inproceedings{c4e1d2292ba84a3396265c09638a15ec,
title = "An approximation algorithm for the smallest color-spanning circle problem",
abstract = "To find a minimum radius circle in which at least one point of each color lies inside, we have researched the smallest enclosing circle problem for n points with m different colors. The former research proposed a π-approximation algorithm with a running time O(n2 + nmlogm). In this paper, we construct a color-spanning set for each point and find the smallest enclosing circle to cover all points of each color-spanning set. The approach to find each color-spanning set is based on the nearest neighbor points which have different colors. An approximation algorithm to compute the minimum diameter of the enclosing circle is proposed with the time of O(nmlog n + n logm) at most. The approximation ratio of our algorithm is less than 2. In conclusion, both approximation ratio and complexity are improved by our proposed algorithm.",
keywords = "Approximation algorithm, Colored set, Computational geometry, The minimum diameter color-spanning set problem",
author = "Yin Wang and Yinfeng Xu",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 21st International Conference on Computing and Combinatorics Conference, COCOON 2015 ; Conference date: 04-08-2015 Through 06-08-2015",
year = "2015",
doi = "10.1007/978-3-319-21398-9\_14",
language = "英语",
isbn = "9783319213972",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "171--182",
editor = "Dachuan Xu and Donglei Du and Dingzhu Du",
booktitle = "Computing and Combinatorics - 21st International Conference, COCOON 2015, Proceedings",
}