CST

Monopolar

Algorithm

• \(d\leftarrow \infty; u\leftarrow\) None
• For all p in P: O(n)
  • Find the two points i,j furthest from p: \(O(n)\)
  • If \(|p,i| + |p,j|\) < \(d \): \(O(1)\)
    • d \(\leftarrow |p,i| + |p,j|\)
    • u \(\leftarrow p\)
• Return unipolar MST formed from u.

Runtime: \(O(n^2)\).

Correctedness

We consider all possible poles. The MST and diameter are unique given a pole. Clearly when we return the minimum over all of these trees we find the overall minimum diameter MST.

Dipolar

We want to do a process similar to above with all pair of points. In order to do so, we need an efficient way of calculating the diameter of a MST given poles \(i,j\), which we refer to as \(T_{ij}\).

Let \(P_i, P_j\) be the points connected to \(i,j\) respectively in \(T_{ij}\). The diameter of the MST \(d(T_{ij}) = \max_{p \in P_i} |ip| + \max_{p \in P_j} |jp| + |ij|\). We can view our task as essentially centering a circle at each pole such that all points are covered by a circle, and the sum of the radii is minimum. We denote our two radii \(L_r, R_r\) for the circle centered at \(i,j\) respectively.

Our radii are always going to be defined by an edge between our pole and points \(\in P-\{i,j\}\). This is evident -- we're seeking minimum distance so we're not going to go further than the last-covered point. Similarly, if we haven't covered a point we can't have a radius smaller than this edge.

As such, we could simply iterate through all possible pairs and see which gets us the best diameter. This takes us to \(O(n^4)\) however, so we have to try a bit harder. It turns out we can get away with checking far fewer candidate radii.

To see this, assume one circle is fixed and denote it L. Let the points covered by L be denoted \(P_L\). We don't need to consider any point \(\in P_L\) as a potential radius. Among all other candidates, we only need to find the point that is closest to j while covering everything else. This point is simply the furthest non-\(P_L\) point from j.

We can exploit this structure by making our L as big as possible, and then shrinking it point by point. We start with our L radius being the point furthest from i, and then bringing it back point by point. Whenever we stop covering a point with L, we make sure that it is covered by R -- i.

Subroutine: diameter(i,j,P)

Input: i, j, P. i and j are poles. P is a list of our pointset-{i,j} sorted in decreasing order WRT distance to i.

• Remove the first element from P and denote it x
• \(L_r\leftarrow |i, x|\), \(R_r\leftarrow 0\).
• \(L_p \leftarrow x\)
• d \(\leftarrow L_r + R_r\)
• For \(p \in P\): O(n)
  • \(R_r \leftarrow \max \{R_r, |j, L_p|\}\)
  • \(L_r \leftarrow |i,p|\); \(L_p \leftarrow p\)
  • d \(\leftarrow \min \{d, R_r + L_r\}\)
• Return d + |i,j|

Correctedness (of the sub-routine) follows from above -- we consider all radii which could potentially be diameter-defining, and simply return the minimum of all of these. Runtime is \(O(n)\).

Main Algorithm

We note that a poor implementation from this point can still result in \(O(n^3\log n\) runtime if we sort too frequently. As such, we sort after choosing each i -- not after choosing a pair i,j. That is:

• a,b=None; d=\(\infty\)
• For all points i \(\in P\): O(n)
  • \(P_s \leftarrow\) P-{i} sorted by decreasing distance t i: \(O(n \log n)\)
  • For all points j \(\in\) P-{i}: O(n)
    • Remove j from \(P_s\): O(n)
    • If di = diameter\((i,j,P_s)\) < d: O(n)
      • d = di; a=i; b=j
    • Add j to \(P_s\): O(n)
• Return the dipolar MST formed by poles a and b. We can find which points to connect to which poles by following the same process as the diam subroutine.

Runtime of \(O(n \left( n\log n + n \left( n\right) \right)) = O(n^3) \)

Correctedness

Correctedness is an immediate property of our arguments above. For all possible pair-of-points, we consider all potential radius-definiing points. By finding the minimum over all of these combinations we are guaranteed to solve our problem.