I read a paper from John Hershberger with this title: "Minimizing the sum of diameters efficiently". 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?
