Separation Distance

We make use of an algorithmic primitive: the Euclidean Mininum Spanning Tree (EMST). An EMST is a MST of points in the plane where the edge-weights are equal to the euclidean distance between the two end-points. This can be found in \(O(n \log n)\) in the algebraic-decision tree model\cite{Buchin_2011}.

Algorithm and Runtime

• Calculate the convex hulls of P and Q. Denote the vertices on-hull V(P) and V(Q): O(n log n).
• Run EMST on \(V(P) \cup V(Q)\): O(n log n)
• Search the EMST for the edge which connects some p from V(P) with some q from V(Q): O(n)
• Check to see if this edge intersects any of the edges in our convex hulls. Convexity guarentees that it will intersect at most once per hull. If we find an intersection on V(P), update the P endpoint of our edge to this intersection point. Similarly for V(Q): O(n)
• Return the length of our edge.

Correctedness

By running the EMST we find the closest pair of vertices between convex hulls. By performing our intersection check and adjusting our endpoints, we guarantee that we find the closest pair of points between the boundary of the hulls. The largest separation distance is equal to this value. This follows by simple observation: if we push either of the lines out, we've either swallowed up a vertex or an edge (and two vertices) of the hull. The vertices in our hull are elements of the original pointset, so our lines no longer separate P and Q.