<p>I read a paper from <strong>John Hershberger</strong> with this title: <a href="https://www.semanticscholar.org/paper/Minimizing-the-Sum-of-Diameters-Efficiently-Hershberger/77a1c6e7860a50bb67c2b83feef9b978728a498b" rel="nofollow noreferrer">&quot;Minimizing the sum of diameters
efficiently&quot;</a>. That paper proposed a simple algorithm that finds a bipartition of points <span class="math-container">$S$</span> in the plane such that minimize sum of diameters of clusters <span class="math-container">$C_1$</span> and <span class="math-container">$C_2$</span>.</p>
<p>According to <strong>John Hershberger</strong> paper, at the first, the paper gives some definitions:</p>
<blockquote>
<p>Let <span class="math-container">$S$</span> be a set of <span class="math-container">$n$</span> points in the plane, let the distance between two
points <span class="math-container">$p$</span> and <span class="math-container">$q$</span> be <span class="math-container">$d(p, q)$</span>, and let the diameter of a set <span class="math-container">$X$</span> be denoted
by <span class="math-container">$Diam(X) = \max\{d(p, q)\mid p, q \in X\}$</span>. The closed disk with radius <span class="math-container">$r$</span>
centered on a point <span class="math-container">$p$</span> is denoted by <span class="math-container">$D(p, r)$</span>. For brevity, we refer to
the sum of the diameters of the components of a bipartition as the
<em>diameter sum</em> of the bipartition. We say that any bipartition with
diameter sum less than <span class="math-container">$Diam(S)$</span> is good. Our algorithm finds the best
of the good partitions, if any good partitions exist.</p>
</blockquote>
<p>After that, the paper describes a straight-forward lemma as follow:</p>
<blockquote>
<p>Lemma 3.1. Let <span class="math-container">$a$</span> and <span class="math-container">$b$</span> be a diametral pair of <span class="math-container">$S$</span>. In any good bipartition of
<span class="math-container">$S$</span>, the subsets are contained in two disjoint disks centered on <span class="math-container">$a$</span>
and <span class="math-container">$b$</span>.</p>
<p>Proof. Let <span class="math-container">$A = d(a, b)$</span>. Any good bipartition of <span class="math-container">$S$</span> must have <span class="math-container">$a$</span> and <span class="math-container">$b$</span> in
different sets, which we denote by <span class="math-container">$S_a$</span> and <span class="math-container">$S_b$</span>. Let <span class="math-container">$r$</span> be the distance
from <span class="math-container">$a$</span> to the point in <span class="math-container">$S$</span>, farthest from it. The set <span class="math-container">$S$</span>, lies in the
disk <span class="math-container">$D(a, r)$</span>. Because <span class="math-container">$Diam(S_a)\geq  r$</span>, we must have <span class="math-container">$Diam(S_b) &lt; \delta - r$</span>, and
hence <span class="math-container">$S_b\subset D(b, A - r - \epsilon)$</span> for some positive <span class="math-container">$\epsilon$</span>. This proof remains
valid even when <span class="math-container">$r = 0$</span>, i.e., <span class="math-container">$\mid S_a\mid= 1$</span>.</p>
</blockquote>
<p><strong>Next, it describes the algorithm as follow:</strong></p>
<p>The algorithm begins by computing a diametral pair <span class="math-container">$a$</span> and <span class="math-container">$b$</span> of <span class="math-container">$S$</span>, which takes
<span class="math-container">$O(n \log n)$</span> time [18]. Next, it sorts the points of <span class="math-container">$S\setminus\{a, b\}$</span> into two lists <span class="math-container">$L_a$</span>, and <span class="math-container">$L_b$</span>,
one sorted by increasing distance from <span class="math-container">$a$</span> and the other by increasing distance
from <span class="math-container">$b$</span>. <strong>Lemma 3.1</strong> implies that for any good bipartition, the points in <span class="math-container">$S_a$</span>, must be
a prefix of <span class="math-container">$L_a$</span>, and a suffix of <span class="math-container">$L_b$</span> (their order may differ in the two lists). The
algorithm identifies all prefixes of <span class="math-container">$L_a$</span>, whose elements form a suffix of <span class="math-container">$L_b$</span>. To do
this, it first marks each element of <span class="math-container">$L_a$</span>, with its rank in <span class="math-container">$L_b$</span>, then prepares an empty
array corresponding to the list <span class="math-container">$L_b$</span>. The algorithm marches through the elements
of <span class="math-container">$L_a$</span>, at each step marking the array entry given by the element’s rank in <span class="math-container">$L_b$</span>.
Whenever a suffix of the array is marked, the algorithm detects it using <strong>union-find</strong>. This takes <span class="math-container">$O(n)$</span> total time, or <span class="math-container">$O(n \log n)$</span> time using a simpler
the algorithm based on a static binary tree.</p>
<p><strong>Now my problem starts from there and I can't understand the continuation of the algorithm:</strong></p>
<p>To compute the diameter sum for all potentially good partitions, we use
Bentley’s logarithmic method maintains the diameter under a sequence of
insertions. We insert the elements of <span class="math-container">$L_a$</span>, into <span class="math-container">$S_a$</span>, in order, to record the
diameter of the set as it changes. We do the same for <span class="math-container">$L_b$</span>. For each prefix of <span class="math-container">$L_a$</span>
whose elements form a suffix of <span class="math-container">$L_b$</span>, we add the two corresponding diameters.
The minimum sum gives the best partition. Using the farthest-point Voronoi
diagram as the basis for the logarithmic method, we get a data structure
with query time and amortized insertion time both equal to <span class="math-container">$O(\log^2 n)$</span>.</p>
<p><strong>Anyone can help me to understand the last part of the algorithm to find out how the algorithm works?</strong></p>

CC BY-SA 4.0
2022-02-21T22:58:24.650Z
What part(s) specifically within the last part don't you understand?  E.g. is it Bentley's logarithmic method (see e.g. [here](https://cstheory.stackexchange.com/questions/7642/i-dreamt-of-a-data-structure-does-it-exist) or [here](https://jeffe.cs.illinois.edu/teaching/datastructures/notes/01-statictodynamic.pdf))?  The last part computes for each prefix of $L_a$ the diameter of that prefix, and likewise for $L_b$, in total time $O(n\log^2 n)$.  By the observation from the previous part, this is enough to answer the question.
Neal Young
CC BY-SA 4.0
2022-02-22T03:59:39.287Z
@NealYoung What is means "their order may differ in the two lists"? I can't understand very well this sentence. I think it say, elements that form a prefix of $L_a$ should be suffix of $L_b$ but I can't understand "their order may differ in the two lists".
ErroR
CC BY-SA 4.0
2022-02-22T13:25:48.797Z
In $L_a$ they are ordered by distance from $a$.  In $L_b$ they are ordered by distance from $b$.  These orders are of course different, but also the reverse of these orders can be different.  Try some examples.  This needs to be taken into account when applying the previous observation, that the partition will consist of some prefix of $L_a$ and some prefix of $L_b$ *such that prefix of $L_a$ and the prefix of $L_b$ exactly partition the set of points*.  (For example, it is not the case that, for each prefix of $L_a$, the points in the remaining suffix of $L_a$ will form a prefix of $L_b$.)
Neal Young
CC BY-SA 4.0
2022-02-23T04:47:02.043Z
@NealYoung Thank you. Also, I can't understand why this algorithm finds an optimal solution? Can you please give me some explanation about the proof of correctness and optimality of the algorithm? I read many time the paper, but I can't find out.
ErroR
CC BY-SA 4.0
2022-02-23T14:00:11.793Z
Jut, the proof in the paper seems correct, and relatively accessible.  My general advice would be to find some courses in algorithms that you can take, where you can get some help learning to understand and work with proofs of correctness.
Neal Young
CC BY-SA 4.0
2022-02-28T08:21:18.563Z
@NealYoung Can you address that where is the proof in the paper? Thank you. I can't find it.
ErroR
CC BY-SA 4.0
2022-02-28T13:07:41.293Z
Lemma 3.1 and the following two paragraphs.  It is informal, but complete.
Neal Young
CC BY-SA 4.0
2022-03-26T15:09:10.050Z
@NealYoung Thank you I really appreciate your help. If you are agree, can you again read my post? I edit the post and I encounterd another problem.
ErroR
CC BY-SA 4.0
2022-03-27T17:03:53.397Z
But there might not be any minimum-cost solution where the two parts have the same size.  Or do you mean, among clusterings into two equal-size clusters, find one of minimum cost?  This seems like a nice question, but its a new question so you'd have to make a new post.
Neal Young
CC BY-SA 4.0
2022-04-01T17:48:20.987Z
@NealYoung Thank you for your suggestion. I post the new question at this link. My goal is to partition points into equal size clusters. You can see the question at https://cstheory.stackexchange.com/questions/51279/partition-points-into-two-equal-clusters
ErroR
CC BY-SA 4.0
2022-04-01T18:48:07.977Z
Any help would be greatly appreciated.
ErroR
<ds.algorithms><computational-geometry>
A problem in understanding an algorithm
ErroR
# A problem in understanding an algorithm

(Asked by: username_0 on 2022-02-21)

I read a paper from **John Hershberger** with this title: ["Minimizing the sum of diameters
efficiently"](https://www.semanticscholar.org/paper/Minimizing-the-Sum-of-Diameters-Efficiently-Hershberger/77a1c6e7860a50bb67c2b83feef9b978728a498b). That paper proposed a simple algorithm that finds a bipartition of points $S$ in the plane such that minimize sum of diameters of clusters $C\_1$ and $C\_2$.

According to **John Hershberger** paper, at the first, the paper gives some definitions:

> Let $S$ be a set of $n$ points in the plane, let the distance between two
> points $p$ and $q$ be $d(p, q)$, and let the diameter of a set $X$ be denoted
> by $Diam(X) = \max\{d(p, q)\mid p, q \in X\}$. The closed disk with radius $r$
> centered on a point $p$ is denoted by $D(p, r)$. For brevity, we refer to
> the sum of the diameters of the components of a bipartition as the
> *diameter sum* of the bipartition. We say that any bipartition with
> diameter sum less than $Diam(S)$ is good. Our algorithm finds the best
> of the good partitions, if any good partitions exist.

After that, the paper describes a straight-forward lemma as follow:

> Lemma 3.1. Let $a$ and $b$ be a diametral pair of $S$. In any good bipartition of
> $S$, the subsets are contained in two disjoint disks centered on $a$
> and $b$.
>
> Proof. Let $A = d(a, b)$. Any good bipartition of $S$ must have $a$ and $b$ in
> different sets, which we denote by $S\_a$ and $S\_b$. Let $r$ be the distance
> from $a$ to the point in $S$, farthest from it. The set $S$, lies in the
> disk $D(a, r)$. Because $Diam(S\_a)\geq r$, we must have $Diam(S\_b) < \delta - r$, and
> hence $S\_b\subset D(b, A - r - \epsilon)$ for some positive $\epsilon$. This proof remains
> valid even when $r = 0$, i.e., $\mid S\_a\mid= 1$.

**Next, it describes the algorithm as follow:**

The algorithm begins by computing a diametral pair $a$ and $b$ of $S$, which takes
$O(n \log n)$ time [18]. Next, it sorts the points of $S\setminus\{a, b\}$ into two lists $L\_a$, and $L\_b$,
one sorted by increasing distance from $a$ and the other by increasing distance
from $b$. **Lemma 3.1** implies that for any good bipartition, the points in $S\_a$, must be
a prefix of $L\_a$, and a suffix of $L\_b$ (their order may differ in the two lists). The
algorithm identifies all prefixes of $L\_a$, whose elements form a suffix of $L\_b$. To do
this, it first marks each element of $L\_a$, with its rank in $L\_b$, then prepares an empty
array corresponding to the list $L\_b$. The algorithm marches through the elements
of $L\_a$, at each step marking the array entry given by the element’s rank in $L\_b$.
Whenever a suffix of the array is marked, the algorithm detects it using **union-find**. This takes $O(n)$ total time, or $O(n \log n)$ time using a simpler
the algorithm based on a static binary tree.

**Now my problem starts from there and I can't understand the continuation of the algorithm:**

To compute the diameter sum for all potentially good partitions, we use
Bentley’s logarithmic method maintains the diameter under a sequence of
insertions. We insert the elements of $L\_a$, into $S\_a$, in order, to record the
diameter of the set as it changes. We do the same for $L\_b$. For each prefix of $L\_a$
whose elements form a suffix of $L\_b$, we add the two corresponding diameters.
The minimum sum gives the best partition. Using the farthest-point Voronoi
diagram as the basis for the logarithmic method, we get a data structure
with query time and amortized insertion time both equal to $O(\log^2 n)$.

**Anyone can help me to understand the last part of the algorithm to find out how the algorithm works?**

**Tags:** ds.algorithms, computational-geometry

> **Comments:**
> **username_1**: What part(s) specifically within the last part don't you understand?  E.g. is it Bentley's logarithmic method (see e.g. [here](https://cstheory.stackexchange.com/questions/7642/i-dreamt-of-a-data-structure-does-it-exist) or [here](https://jeffe.cs.illinois.edu/teaching/datastructures/notes/01-statictodynamic.pdf))?  The last part computes for each prefix of $L_a$ the diameter of that prefix, and likewise for $L_b$, in total time $O(n\log^2 n)$.  By the observation from the previous part, this is enough to answer the question.  
> **username_0**: @NealYoung What is means "their order may differ in the two lists"? I can't understand very well this sentence. I think it say, elements that form a prefix of $L_a$ should be suffix of $L_b$ but I can't understand "their order may differ in the two lists".  
> **username_1**: In $L_a$ they are ordered by distance from $a$.  In $L_b$ they are ordered by distance from $b$.  These orders are of course different, but also the reverse of these orders can be different.  Try some examples.  This needs to be taken into account when applying the previous observation, that the partition will consist of some prefix of $L_a$ and some prefix of $L_b$ *such that prefix of $L_a$ and the prefix of $L_b$ exactly partition the set of points*.  (For example, it is not the case that, for each prefix of $L_a$, the points in the remaining suffix of $L_a$ will form a prefix of $L_b$.)  
> **username_0**: @NealYoung Thank you. Also, I can't understand why this algorithm finds an optimal solution? Can you please give me some explanation about the proof of correctness and optimality of the algorithm? I read many time the paper, but I can't find out.  
> **username_1**: Jut, the proof in the paper seems correct, and relatively accessible.  My general advice would be to find some courses in algorithms that you can take, where you can get some help learning to understand and work with proofs of correctness.  
> **username_0**: @NealYoung Can you address that where is the proof in the paper? Thank you. I can't find it.  
> **username_1**: Lemma 3.1 and the following two paragraphs.  It is informal, but complete.  
> **username_0**: @NealYoung Thank you I really appreciate your help. If you are agree, can you again read my post? I edit the post and I encounterd another problem.  
> **username_1**: But there might not be any minimum-cost solution where the two parts have the same size.  Or do you mean, among clusterings into two equal-size clusters, find one of minimum cost?  This seems like a nice question, but its a new question so you'd have to make a new post.  
> **username_0**: @NealYoung Thank you for your suggestion. I post the new question at this link. My goal is to partition points into equal size clusters. You can see the question at https://cstheory.stackexchange.com/questions/51279/partition-points-into-two-equal-clusters  
> **username_0**: Any help would be greatly appreciated.  

---

## 0 answers

