The approximation algorithms for a class of multiple-choice problem

Given a set of n points, which is a unit set of m colored sets, we study the minimum circle to cover one of each colored set at least. In this paper, we study some problems of optimizing some properties of color-spanning set. Firstly, we show a way to find a color-spanning set for each point and constitute a union of color-spanning sets without FCVD (The Farthest Color Voronoi Diagram). The approach to find each color-spanning set is based on the nearest neighbor points which have different colors. For every color-spanning set, we can find a enclosing circle to cover all points of each color-spanning set, which is a good approximate for MDCS (The Minimum Diameter Color-Spanning Set) problem. We propose an approximation algorithm for the SECSC (The Smallest Color-Spanning Circle) problem with 2-factor approximation result. For |P|=n and |Q|=m, the worst running time of our algorithm is O(n²). Although these results are not as good as previous results with FCVD, the performance of our algorithms in R^d is much better than others. Moreover, an approximation algorithm can solve problem of minimum perimeter of the color-spanning set faster with time of O(n²+nmlog⁡n) and ratio 6. This result improved the ratio with only a little cost of time complexity. At last, we give an example for the 2-center SECSC problem. A fast computation of 2-center enclosing circle is proposed with time of O(n²), but the ratio depends on the gap between the nearest distinct colored distance.