Xavier Holt edited CST_Monopolar_Consider_every_point__1.md  almost 8 years ago

Commit id: ee2bd205cd64506855cc9f35900c984a1ac4d4ec

deletions | additions      

       

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 \in  P_i} |ip| + \max_{p \ in \in  P_j} |jp| + |ij|\).