We are given a set of points X $=\{$x$1,...,$ xn$\}$ where xi in Rd for all i in $[$n$].$ This set gives rise to a graph where V $=$ X and E $=$ V $$ V $,$ i$.$e$.,$ all edges exist. For each edge $($i$,$ j$),$ the weight is the Euclidean distance w$($i$,$ j$)=$xi $$ xj $\_2.$

We are tasked with computing a minimum spanning tree $($MST$)$ using the Kruskal method that we learned in class, which works in O$($n$^2)$ time for this graph if we know all weights.

Assuming that computing w$($i$,$ j$)$ takes O$($d$)$ time, precomputing all weights will take O$($n$^2$d$).$ The total time of this method is O$($n$^2$d$).$

Unfortunately, d $=($n$^1\mathrm{.}2)$ is much larger than n$,$ so this total time is prohibitively expensive. Can you improve the running time if we allow an approximate solution?

That is$,$ we want to output a tree at most a factor of $(1+$ $)$ more expensive than the

MST but would work in o$($n$2$d$).$ You can assume that $=0\mathrm{.}0001.$

Prove the correctness of your algorithm and explain the running time.