Form a pointset of all circle centers. Use a WSPD to find the closest pair of centers \(O(n\log n)\). Return `disjoint`

if the distance between these points is > 1, `non-disjoint`

else.

Disjoint circles

\(\iff\) all pairwise circle centers are > 1 dist apart (unit circles, r=1)

\(\iff\) the closest pair of points is > 1 dist apart \(\square\).

- \(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\)

- Find the two points
- Return unipolar MST formed from
`u`

.

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

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.

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.

**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)\).

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 = < d: O(n)
- d = di; a=i; b=j

- Add
`j`

to \(P_s\): O(n)

- Remove

- \(P_s \leftarrow\)
- 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 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.

## Share on Social Media