We study geometric graph problems in the parallel/distributed setting. For
example, for the Minimum Spanning Tree problem over a set of points in
two-dimensional space, our algorithms output a (1+epsilon)-approximate solution.
Our algorithms work in a constant number of rounds of communication, while using
total space and communication proportional to the size of the data (linear
algorithms). In contrast, for general graphs, achieving the same result for MST
(or even connectivity) remains a challenging open problem, despite drawing
significant attention in recent years.

We leverage space partitioning techniques to parallelize the computation. Our
approach is inspired by streaming algorithms for estimating the solution cost
(but where it is usually impossible to output the solution).