覆盖n个点的最小圆数

Question

1. 将求解第一个点的第一个圆放置在适当位置。
2. 通过检查这两个点之间的距离是否小于2*r来求解最小圈数中的第二个点。并继续处理所有n个点。我认为是贪婪算法，但它是最优的，线性的吗？

Answer 1

我能想到的最简单的方法就是，把你的点放在一个数组里。

在每个点上迭代，增加它与前一个点之间的距离，直到累积的距离大于2R。

添加到全局计数器中。重置距离，重复。

count = 1
last_point = point_list[0]
distance = 0
for(point in point_list)
   distance += norm(point - last_point)
   if(distance >= 2r)
     count++
     distance = 0
   last_point = point

由于堆栈溢出不会格式化latex,您将不得不接受原样的latex表示法。

假设我们有一组点$P$。假设$D=max(P_I-P_J)$其中$p_i,p_j\in P$。如果$D<2R$,则radius R的某个磁盘$C$的$P\子集C$。

给定一个新点$q\notin p$如果$max(q-p)<2r$其中$p\在p$中存在$\则$$磁盘$D$使得${q}\cup p\子集d$。

然后参考前面部分中描述的算法。每当一个连续点序列的跨度小于$2R$时，$\就存在一个包含这些点的磁盘（由前面的参数）。如果在序列中找到一个新点，使得它到最远点的距离大于$2R，那么就需要一个额外的圆（同样由引理1）。

引理2假设，要知道是否需要一个新的圆，我们只需要关注最后一组点，前提是我们已经按顺序访问了这些点（从而访问了这些集合）。如果一个新点与最后一个集合中最远的点的距离小于2r，则不需要新的圆，否则就需要一个新的圆（根据引理1)，因此我们将注意力集中在这个新点（及其关联的集合）上。

我们这样做，直到所有的点都访问过。