Xavier Holt edited Algorithm_This_leads_to_a__.md  almost 8 years ago

Commit id: fbe613dee317a47bb1aaab3f2f5776b14722bb42

deletions | additions      

       

### Algorithm  This leads to a simple approximation algorithm. If we set `s` to \(\frac{8}{\epsilon}\), then one of our   * 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\). \epsilon^{-1}n)\).  * d \(\leftarrow \infty\); `M` = `None`  * For pairs `A`,`B` in `W`: \(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)\)  * if `t` < `d`:  * `d` = `t`; `M` = a-b dipolar MST  * 'Calculate and compare to unipole trees': \(O(n^2)\)  * Return `M`.  *