Xavier Holt edited Algorithm_This_leads_to_a__.md  almost 8 years ago

Commit id: 40d8fef371cdff9d0509ddee919698b10121843e

deletions | additions      

       

* W \(\leftarrow\) WSPD decomp of \(P\) with \(s = \frac{8}{\epsilon}\). We note that \(s \in O(e^{-1})\). As such construction takes \(O(n \log n + \epsilon^{-1}n)\).  * d \(\leftarrow \infty\); `M` = `None`  * For pairs `A`,`B` in `W`: \(O(\epsilon^{-1}n\) \(O(\epsilon^{-1}n)\)  * `a`,`b` \(\leftarrow\) points sampled from `A`,`B` resp.  * S \(\leftarrow\) `P-{a}` sorted w.r.t. increasing distance to `a`: \(O(n\log n)\)  * t \(\leftarrow \text{diameter}(a,b,S)\): \(O(n)\)