Algorithm

• 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^{-2}n)\).
• d \(\leftarrow \infty\); M = None
• For pairs A,B in W: \(O(\epsilon^{-2}n)\)
  • a,b \(\leftarrow\) points sampled from A,B resp.
  • S \(\leftarrow\) P-{a} sorted by decreasing 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.

Runtime is \(O(n^2 \epsilon^{-2} \log n)\).

Correctedness follows primarily from the above arguments. There has to be one pair in our WSPD such that regardless of the poles a,b sampled, we have \(\text{diam}(a,b)\leq (1 + \frac{8}{s}) OPT = (1+\epsilon) OPT\). As we sample poles from every WSPD pair, it follows that we will find a tree that matches this bound.