寻找一组点与圆盖 [英] Finding a cover of a set of points with circles

问题描述

予有N个点中通过坐标和一个数K给定的一个集合V（0℃，K＆其中N）。我需要确定K值圈（磁盘）具有相同的半径为R，其中心在V设定点。这些圈有盖所有的N个点，R是最小的可能。

I have N points in a set V given by their coordinates and a number K (0 < K < N). I need to determine K circles (disks) with the same radius R, with their centers in points in the V set. These circles have to 'cover' all the N points and R is the smallest possible.

谁能帮助我？

推荐答案

这个问题就是所谓的（离散）$ķ$中心问题，并在集群一个众所周知的问题。而问题是在一般的NP完全，有一个很容易的算法产生在任何度量内的最佳解决方案的因子2溶液（含问题的暗示的2-D欧几里德距离）。它是由于冈萨雷斯，并且是如下

This problem is known as the (discrete) $k$-center problem, and is a well known problem in clustering. While the problem is in general NP-complete, there is a very easy algorithm that generates a solution within factor 2 of the optimal solution in any metric (including the implied 2-D Euclidean distance of the question). It is due to Gonzalez, and is as follows

1. 在选取任意点
2. 找到它的最远的邻居
3. 从这两
找到点最远
4. 等，直到你有k个点。

你最终的半径R是这最后一点到下一个最远点的距离。通过构造，可以保证覆盖所有的点半径盘集中在各k个点，并通过三角不等式此R是内2的最佳半径的因素。

The radius R you end up with is the distance from this last point to the next farthest point. By construction, you are guaranteed to cover all points with disks of radius centered at each of the k points, and by triangle inequality this R is within a factor of 2 of the optimal radius.

如果你知道你是在飞机上，你可以做在理论上有所好转（包括得到一个确切的算法，在多项式时间的N和指数的K），但在实践中，上述算法很可能是最简单的

If you know that you're in the plane, you can do somewhat better in theory (including getting an exact algorithm in time polynomial in n and exponential in k), but in practice the above algorithm is likely to be the easiest

这篇关于寻找一组点与圆盖的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！