<p>This problem indeed seems very suitable for property testing:</p>
<p><strong>Claim:</strong> If the diameter of P is more than 2D and we cannot make the diameter of P 2D or less by removing εn points in P, then we can find <span class="math-container">$O(\varepsilon (1-\varepsilon) n^2)$</span> pairs of points at distance <span class="math-container">$\geq D$</span>.</p>
<p><em><strong>Proof:</strong></em> Take two points so that their distance is at least <span class="math-container">$2D$</span>.
Every point <span class="math-container">$p$</span>, is at distance <span class="math-container">$\geq D$</span> of one of the two points, by triangular inequality. We therefore obtain <span class="math-container">$n$</span> pairs of points, containing one of those two, at distance <span class="math-container">$\geq D$</span> of each other.
Then remove the two points and repeat the process, until the diameter is <span class="math-container">$\leq 2D$</span>.
This takes at least <span class="math-container">$\epsilon n /2$</span> iterations, by the assumption in the statement of the claim.
Hence in total we obtain at least <span class="math-container">$n + n-2 + ... + n-(2\lfloor \varepsilon n/2 \rfloor)$</span> pairs of points at distance <span class="math-container">$\geq D$</span>, that is, <span class="math-container">$O(\varepsilon (1-\varepsilon) n^2)$</span>.
Note that this bound is tight, we can reach it by having two far away packs of close points, one of <span class="math-container">$\varepsilon n$</span> points and the other with <span class="math-container">$(1-\varepsilon) n$</span> points.</p>
<p>Now the algorithm:
You can sample <span class="math-container">$\frac{1}{\varepsilon(1-\varepsilon)}$</span> pairs of points at random: if one of these pairs <span class="math-container">$(p_1, p_2)$</span> is such that the distance between <span class="math-container">$p_1$</span> and <span class="math-container">$p_2$</span> is more than <span class="math-container">$D$</span> then answer no, otherwise answer yes.</p>
<ul>
<li>If the diameter is <span class="math-container">$D$</span> or less then no such pair of points exists, hence the algorithm answers &quot;yes&quot; with probability 1.</li>
<li>If the diameter is more than <span class="math-container">$2D$</span>, and not reducible under <span class="math-container">$2D$</span> by removing <span class="math-container">$\varepsilon n$</span> points then by the previous claim each sampled pair of points has probability <span class="math-container">$O(\varepsilon(1-\varepsilon))$</span> to be at distance <span class="math-container">$\geq D$</span> of each other.
As we sample <span class="math-container">$O(\frac{1}{\varepsilon(1-\varepsilon)})$</span> pairs we have a constant probability of answering no.</li>
</ul>
<p>Repeating this algorithm a suitable constant number of times reduces the probability of failure in the second case below <span class="math-container">$1/3$</span>.</p>

CC BY-SA 4.0
2024-06-14T10:43:50.767Z
2024-06-14T14:36:01.863Z
2024-06-14T14:36:01.863Z
Corto
<p>given a set of n points P and a nxn matrix M such that for every two point u,v where M[u,v] is the distance between u and v , and the distance is pseudo metric, is there a property testing algorithem such that given a number D &gt;0 and ε in the range (0, 1) returns the following:</p>
<ul>
<li>if the diameter of P is D or less, the algorithem returns &quot;yes&quot; with probability at least 2/3</li>
<li>if the diameter of P is more than 2D and we cannot make the diameter of P to become 2D or less by removing εn points in P , the algorithem returns &quot;no&quot; with probability at least 2/3.</li>
<li>in every other situiation , it doesnt matter what the algorithem answers.</li>
</ul>
<p>i am aware that there is a deterministic algorithem for approximating the diameter by a factor of 2 (The classic 2-approximation algorithm for this problem) that uses running time O(nd), and which is to choose an arbitrary point and then return the maximum distance to another point. The diameter is no smaller than this value and no larger than twice this value.but i cant see a conncection to the given problem .</p>

CC BY-SA 4.0
2024-07-06T06:55:51.737Z
Cross-posted: https://cstheory.stackexchange.com/q/54391/5038, https://math.stackexchange.com/q/4930867/14578.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).
D.W.
<property-testing>
The problem of approximating the diameter of a point set
usul
# The problem of approximating the diameter of a point set

(Asked by: username_0 on 2024-06-11)

given a set of n points P and a nxn matrix M such that for every two point u,v where M[u,v] is the distance between u and v , and the distance is pseudo metric, is there a property testing algorithem such that given a number D >0 and ε in the range (0, 1) returns the following:

* if the diameter of P is D or less, the algorithem returns "yes" with probability at least 2/3
* if the diameter of P is more than 2D and we cannot make the diameter of P to become 2D or less by removing εn points in P , the algorithem returns "no" with probability at least 2/3.
* in every other situiation , it doesnt matter what the algorithem answers.

i am aware that there is a deterministic algorithem for approximating the diameter by a factor of 2 (The classic 2-approximation algorithm for this problem) that uses running time O(nd), and which is to choose an arbitrary point and then return the maximum distance to another point. The diameter is no smaller than this value and no larger than twice this value.but i cant see a conncection to the given problem .

**Tags:** property-testing

> **Comments:**
> **username_1**: Cross-posted: https://cstheory.stackexchange.com/q/54391/5038, https://math.stackexchange.com/q/4930867/14578.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  

---

## 1 answers

### Answer by username_2 on 2024-06-14. Score: 0 | Accepted answer

This problem indeed seems very suitable for property testing:

**Claim:** If the diameter of P is more than 2D and we cannot make the diameter of P 2D or less by removing εn points in P, then we can find $O(\varepsilon (1-\varepsilon) n^2)$ pairs of points at distance $\geq D$.

***Proof:*** Take two points so that their distance is at least $2D$.
Every point $p$, is at distance $\geq D$ of one of the two points, by triangular inequality. We therefore obtain $n$ pairs of points, containing one of those two, at distance $\geq D$ of each other.
Then remove the two points and repeat the process, until the diameter is $\leq 2D$.
This takes at least $\epsilon n /2$ iterations, by the assumption in the statement of the claim.
Hence in total we obtain at least $n + n-2 + ... + n-(2\lfloor \varepsilon n/2 \rfloor)$ pairs of points at distance $\geq D$, that is, $O(\varepsilon (1-\varepsilon) n^2)$.
Note that this bound is tight, we can reach it by having two far away packs of close points, one of $\varepsilon n$ points and the other with $(1-\varepsilon) n$ points.

Now the algorithm:
You can sample $\frac{1}{\varepsilon(1-\varepsilon)}$ pairs of points at random: if one of these pairs $(p\_1, p\_2)$ is such that the distance between $p\_1$ and $p\_2$ is more than $D$ then answer no, otherwise answer yes.

* If the diameter is $D$ or less then no such pair of points exists, hence the algorithm answers "yes" with probability 1.
* If the diameter is more than $2D$, and not reducible under $2D$ by removing $\varepsilon n$ points then by the previous claim each sampled pair of points has probability $O(\varepsilon(1-\varepsilon))$ to be at distance $\geq D$ of each other.
  As we sample $O(\frac{1}{\varepsilon(1-\varepsilon)})$ pairs we have a constant probability of answering no.

Repeating this algorithm a suitable constant number of times reduces the probability of failure in the second case below $1/3$.


---

