Minimum number of circles to cover n points

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

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.

In pseudocode:

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

Proof

Base case: It works for n = 1, trivially

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

Assume that a new point is introduced to the line.

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

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.

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.

Verbose proof

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

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.

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$.

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.

This is lemma 1.

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$.

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$.

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.

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$.

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$.

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}$.

this is lemma 2.

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).

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 :^))

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top