论文标题
最小颜色跨度不精确点
Minimum color spanning circle of imprecise points
论文作者
论文摘要
令$ \ cal r $为一组$ n $彩色的不精确点，每个点都由$ k $颜色之一颜色。每个不精确的点由该点所在的单位磁盘指定。我们研究了计算其相应磁盘内所有可能的点选择中最小和最大可能的最小颜色跨度圆的问题。我们提供一个$ O（NK \ log N）$时间算法来计算最小的最小颜色跨度圆圈。关于最大的最小颜色跨度圆圈，我们表明问题是NP-HARD，并提出了$ \ frac {1} {3} $ - 因子近似算法。对于没有不同颜色相交的两个磁盘，我们将近似因子提高到$ \ frac {1} {2} $。
Let $\cal R$ be a set of $n$ colored imprecise points, where each point is colored by one of $k$ colors. Each imprecise point is specified by a unit disk in which the point lies. We study the problem of computing the smallest and the largest possible minimum color spanning circle, among all possible choices of points inside their corresponding disks. We present an $O(nk\log n)$ time algorithm to compute a smallest minimum color spanning circle. Regarding the largest minimum color spanning circle, we show that the problem is NP-Hard and present a $\frac{1}{3}$-factor approximation algorithm. We improve the approximation factor to $\frac{1}{2}$ for the case where no two disks of distinct color intersect.
