this is for holding javascript data
Xavier Holt edited CST_Monopolar_Consider_every_point__1.md
almost 8 years ago
Commit id: 9f221cb21dab8028b72cf5688232b71760fc9357
deletions | additions
diff --git a/CST_Monopolar_Consider_every_point__1.md b/CST_Monopolar_Consider_every_point__1.md
index 8208bbc..78539eb 100644
--- a/CST_Monopolar_Consider_every_point__1.md
+++ b/CST_Monopolar_Consider_every_point__1.md
...
# CST
## Monopolar
Consider every point as a potential pole. For each of these points, find the two points furthest away from ### Algorithm
* \(d\leftarrow \infty; u\leftarrow\) None
...
* u \(\leftarrow p\)
* Return 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 one circle, and the sum of the radii is minimum.
We define \(L_r:=\max_{p \in P_i} |ip|; R_r:=\max_{p \in P_j} |jp|\)
Our radii are always going to be defined by points \(\in P-\{i,j\}\). 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.