An Approximation Algorithm for the Smallest Color-Spanning Circle Problem

作者：Wang Yin^*; Xu Yinfeng

来源：21st International Computing and Combinatorics Conference (COCOON), 2015-08-04 to 2015-08-06.

DOI：10.1007/978-3-319-21398-9_14

• Computational geometry
• Colored set
• Approximation algorithm
• The minimum diameter color-spanning set problem

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 pi-approximation algorithm with a running time O(n(2) + nm log m). 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(nm log n + n log m) 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.

• 出版日期2015
• 单位西安交通大学