Xavier Holt edited CST_Monopolar_Consider_every_point__1.md  almost 8 years ago

Commit id: 3f1069628e3815b5c482d54768e822e1f47c02d9

deletions | additions      

       

### Main Algorithm  * a,b=None; d=\(\infty\)  * For all points i: O(n)  * \(P_s \leftarrow\) `P-{i}` sorted in increasing distance WRT `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.