涵盖n点的最小圆数 [英] Minimum number of circles to cover n points

问题描述

要覆盖所有n个点且n个点在一条直线上，半径为r的最小圆数是多少?

What is the minimum number of circles with radius r needed to cover all n points, while the n points are on a straight line?

我知道有人问过类似的问题 在这里之前. 半径为r的可覆盖n的最小圆数点

I know that there is a similar question that was asked before here. Minimum number of circles with radius r to cover n points

我的尝试:我想在线性时间内解决它， 我考虑过这种算法:

My attempt : I'm trying to solve it in a linear time , I thought about this algorithm :

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

1. place the first circle in place that solve for the first point.
2. solve for the second point in the minimum number of circles by checking if the distance between these two points is less than 2*r. and continue in the processes for all n-points. I think it's greedy algorithm , but is it optimal and linear?

推荐答案

我能想到的最简单的方法是将您的点放在一个数组中.

The simplest way I can think of is, have your points in an array.

在每个点上进行迭代，将其与上一个点之间的距离向上迭代，直到累积距离大于2r.

Iterate over each point adding the distance between it and the prior point, up and until the accumulated distance is more than 2r.

添加到全局计数器中.重设距离，重复.

Add to a global counter one. reset the distance, repeat.

使用伪代码:

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

证明

基本情况: 它适用于n = 1，很简单

Proof

Base case: It works for n = 1, trivially

归纳案例: 假设它适用于n个案例(最多k个案例)

Inductive case: Assume it works for n up to k cases

假定将新点引入线.

情况1，该点在最后计算的圆的内部.然后在循环的下一次迭代中，if语句中的条件不满足，计数不增加，算法返回正确的答案

Case 1, the point is within the interior of the last calculated circle. Then on the next iteration of the loop the condition in the if statement is not satisfied, the count doesn't go up, the algorithm returns the correct answer

情况2，该点在最后计算的圆的内部之外. 然后，由于其他k个元素的覆盖范围最小，因此无法重新排列圆圈以覆盖新点.因此，我们必须引入一个新圈子.

Case 2, the point is outside the interior of the last calculated circle. Then, since the covering for the other k elements was the minimum, it is impossible to rearrange the circles to cover the new point. So we must introduce a new circle.

在这种情况下，如果满足if的条件，则计数加一.我们再次返回正确的数字.

In this case the condition of the if is satisfied, the count goes up by one. We return the correct number once again.

我们已经证明了归纳法.

We have proven the inductive case.

由于堆栈溢出不会格式化乳胶，因此您必须按原样接受乳胶符号.

You will have to accept the latex notation as is since stack overflow does not format latex.

假设我们有一组点$ P $.假设$ d = max(|| p_i-p_j ||)$其中$ p_i，p_j \ in P $.如果$ d<半径为r的某些磁盘$ C $的2r $ $ P \ subset C $.

Assume we have a set of points $P$. Assume that $d = max(||p_i - p_j||)$ where $p_i, p_j \in P$. If $d < 2r$ the $P \subset C$ for some disk $C$ of radius r.

给出新点$ q \ notin P $如果$ max(|| q-p ||)< 2r $，其中$ p在P $中，然后$ \存在一个磁盘$ D $，使得$ {q} \ cup P \子集D $.

Given a new point $q \notin P$ if $max(||q - p||) < 2r$ where $p \in P$ then $\exists$ a disk $D$ such that ${q} \cup P \ subset D$.

否则，如果$ max(|| q-p ||)> 2r $则不存在这样的磁盘，否则磁盘中将存在2个点，使得它们的距离大于2r，这是荒谬的.

Otherwise if $max(||q - p||) > 2r$ then no such disk exists, otherwise there would be 2 points in the disk such that their distance is greater than 2r, which is absurd.

这是引理1.

假设我们有一组这样的集合$ S $，即$ s \ in S \ implies s = {x | || x-y || < 2r \ text {if} y \ in s} $.对于所有$ s \ in S $，如果$ x \ in s $则$ x \ in L $其中$ L $是某行.还假设如果$ {x \ in s1 \ in S} $和$ y \ in s2 \ in S $，则$ || x_1-x_2 || > = 2r $.

Assume we have a set of such sets $S$, i.e. $s \in S \implies s = {x | ||x - y|| < 2r \text{if} y \in s}$. And for all $s \in S$ if $x \in s$ then $x \in L$ where $L$ is some line. Assume as well that if ${x \in s1 \in S}$ and $y \in s2 \in S$ then $||x_1 - x_2|| >= 2r$.

由于这些点位于a上，因此按照定义，$ \存在x_0 $和$ \ vec {d} $(单位向量为$ \ vec {d} $)，因此可以相对地对这些点进行排序到$ x_0 $的距离，WLOG假设$ x_0 $是$ S $的点之一，因此$ \ vec {d} \ cdot(x-x_0)\ geq 0 $其中$ x \ in s \ in新币.

Since the points are on a, in a line by definition, $\exists x_0$ and $\vec{d}$ ($\vec{d}$ a unit vector), such that the points can be ordered relative to their distance to $x_0$, WLOG assume $x_0$ is one of the points in $S$, such that $\vec{d} \cdot (x - x_0) \geq 0$ where $x \in s \in S$.

这意味着对于每个集合$ s_i \ in S \存在D_i $，使得$ s_i \子集D_i $和$ D_i \ cap D_j = \ empty $(如果$ i \ neq j $通过构造).磁盘$ {D_i} $的排列良好.

This implies that for each set $s_i \in S \exists D_i$ such that $s_i \ subset D_i$ and $D_i \cap D_j = \empty$ if $i \neq j$, by construction. And that the disks ${D_i}$ are well ordered.

让$ s_ {max} \ in S $为$ \ vec {d} \ cdot(x_ {max}-x_0)\ geq \ vec {d} \ cdot(x_i-x_0)$的集合对于所有此类$ x $，$ x_ {max} \ in s_max $和$ x \ in s \ in S $.或用简单的英语来说，$ s_max $是包含距离$ x_0 $最远的点的集合.

Let $s_{max} \in S$ be the set such that $\vec{d} \cdot (x_{max} - x_0) \geq \vec{d} \cdot (x_i - x_0)$ where $x_{max} \in s_max$ and $x \in s \in S$ for all such $x$. Or in plain english, $s_max$ is the set containing the point furthest from $x_0$.

假设现在将新点$ q $添加到行中，使得其到$ x_0 $的距离大于$ x_max $的距离.

Assume a new point $q$ is now added to the line such that its distance to $x_0$ is larger than that of $x_max$.

在引理1中，圆的总数保持不变或上升1，并且仅在$ max(|| q-x ||)> = 2r $的情况下才上升1，其中$ x \以s_ {max} $.

By lemma 1, either the total number of circles remains constant or it goes up by 1, and will only go up by one if $max(||q - x||) >= 2r$ where $x \in s_{max}$.

这是引理2.

然后参考上一节中描述的算法. 每当连续点的序列小于$ 2r $时，$ \存在包含这些点的磁盘D $(通过先前的参数).如果发现序列中的新点，使其与最远点的距离大于$ 2r $，则需要​​再增加一个圆(同样由引理1表示).

Refer then to the algorithm described in the prior section. Whenever a sequence of consecutive points spans less than $2r$, $\exists D$ a disk containing those points (by the prior argument). If a new point in the sequence is found such that its distance to the furthest point from it is more than $2r$ then one additional circle is needed (again by lemma 1).

引理2假设要知道是否需要一个新的圆，我们只需要关注最后一组点，前提是我们已经按顺序访问了这些点(因此也访问了这些点).如果一个新点在距离上一个集合中最远点的距离内小于2r，则不需要新的圆，否则就需要一个新的圆(通过引理1)，因此我们将重点放在这个新点(及其关联集合)上

Lemma 2 postulates that to know if a new circle is needed we only need to focus on the last set of points, provided we have visited the points (and thus the sets) in order. If a new point is less than 2r within distance of the farthest point in the last set, no new circle is needed, otherwise a new one is needed (by lemma 1) And we thus focus on this new point (and its associated set).

我们这样做直到所有的点都被访问为止.

We do this until all points have been visited.

我们已成功证明该算法是最小的.

We have successfully proven that the algorithm is minimal.

(而且我们不必关心圆圈在哪里:^))

(And that we do not need to care where the circles are :^))

这篇关于涵盖n点的最小圆数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！