Xavier Holt edited CST_Monopolar_Consider_every_point__1.md  almost 8 years ago

Commit id: 1d6c6b59fa66854ffe25cbc7e6cbb65682d8e2e3

deletions | additions      

       

* \(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)\)  ### Main Algorithm  * For all points i:  * \(P_s \leftarrow\) `P-{i}` sorted in increasing distance WRT `i`: \(O(n \log n)\)  * For all points j:  * Remove `j` from \(P_s\): O(n)  * \(d = \min\{ d, \text{diameter}(i,j,P_s) \}\)