Xavier Holt edited CST_Monopolar_Algorithm_d_leftarrow__.md  almost 8 years ago

Commit id: 6156442bd9ae2db61b9a60bf8afe05aa187ccb72

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 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 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.