The $k$-center problem is to choose a subset of size $k$ from a set of $n$ points such that the maximum distance from each point to its nearest center is minimized. Let $Q=\{Q_1,\ldots,Q_n\}$ be a set of polygons or segments in the region-based uncertainty model, in which each $Q_i$ is an uncertain point, where the exact locations of the points in $Q_i$ are unknown. The geometric objects segments and polygons can be models of a point set. We define the uncertain version of the $k$-center problem as a generalization in which the objective is to find $k$ points from $Q$ to cover the remaining regions of $Q$ with minimum or maximum radius of the cluster to cover at least one or all exact instances of each $Q_i$, respectively. We modify the region-based model to allow multiple points to be chosen from a region and call the resulting model the aggregated uncertainty model. All these problems contain the point version as a special case, so they are all NP-hard with a lower bound 1.822. We give approximation algorithms for uncertain $k$-center of a set of segments and polygons. We also have implemented some of our algorithms on a data-set to show our theoretical performance guarantees can be achieved in practice.
翻译:美元中间点问题在于从一组美元点数中选择一个大小的子集 $ 美元, 以便从每个点点到最近的中心点的最大距离最小化。 $1,\ldots, ⁇ n ⁇ $是一组基于区域的不确定性模型中的多边形或区块, 其中每个$是一个不确定点, 其中点的确切位置未知。 几何对象区块和多边形块可以是一组点数的模型。 我们定义了美元中间点问题的不确定版本, 作为一种概括, 目标是从每点点中点中找到美元的最大距离, 从美元中找到美元点数, 以覆盖剩余区域的美元点数, 其范围最小或最大半径为美元。 我们修改区域模型, 允许从一个区域选择多个点数, 并将由此产生的模型称为综合不确定性模型。 所有这些问题都包含点版本, 因此, 它们都是硬点数, 其范围小于1.822。 我们给基于确定性能的模型算法, 我们也可以在一定的方位数中, 显示我们实现的方位数的方程式算。