For our approximation scheme we perform a process similar to the above. The difference is we use a WSPD to consider only a linear number of potential poles.
We assume the optimal spanning tree for our pointset is dipolar. We justify this assumption by noting that after this process is complete, we can use the \(O(n^2)\) algorithm given above to find the optimal unipolar tree and simply return the smaller of the two. This does not impact our overall runtime.
Our strategy is to iterate over all pairs in the decomp. We'll choose a point randomly from each tuple as our two potential poles. We aim to demonstrate that this strategy results in a reasonable diameter tree in the worst case.
Let our two optimal poles be denoted i and j. In our WSPD, there is exactly one pair A,B such that \(i\in A, j\in B\) or vice-versa. Let i' and j' be the points we randomly choose when iterating over the pair A,B.
Again we let \(P_i, P_j\) be the points connected to i and j resp. in the optimal tree. We examine the properties of a tree formed by connecting everything in \(P_i\) to i' instead (similarly for \(P_j\), j').
We justify this strategy by noting that we're going to use our diameter sub-routine. This calculates the optimal diameter with i',j' poles. As such, any particular point-pole connection strategy we choose for analysis will never result in a better diameter than our system.
If we set the radius of the i'-circle to be \(|i,i'| + L_r\) where \(L_r\) was the i-optimal radius we cover all points. This follows from the triangle inequality. For all points \(p\in P_i\), \(|i',p| \leq |i',i| + |i,p| \leq |i',i| + L_r\). We set the j'-radius similarly.
It follows that our diameter is given by the following: \(\text{diam}(i',j')=\left(|i,i'| + L_r \right) + \left(|j,j'| + R_r \right) + |i',j'|\).
We substitute in our WSPD bounds of \(|i,i'| \leq \frac{2}{s}|i,j|\) (resp. \(|j,j'| \leq \dots\) ) and \(|i',j'| \leq (1 + \frac{4}{s}) |i,j|\).