% Not developed further --- result was already known!

\titlestuff{

% Reference macros

The {it Voronoi diagram} of a set $P$ of points in the plane is a well-known concept [\Vor?]. Its dual is the {\it Delaunay triangulation}, in which two points of $P$ are connected iff the corresponding regions of the Voronoi diagram share an edge. We recall the following property of Delaunay triangulations:

\theorem{1}{For any two points $p, q\in P$, the segment $pq$ is an edge of the Delaunay triangulation iff there is a circle that passes through $p$ and $q$, and contains no other point of $P$ (neither on its boundary nor in its interior).}

\mfig4cm
\proof{The segment $pq$ is an edge of the Delaunay triangulation iff there is some point $c$ of the plane that is on the boundary of exactly two regions of the Voronoi diagram, those corresponding to $p$ and $q$. But this is equivalent to saying that $p$ and $q$ are equidistant from $c$, and all other points of $P$ are further away from $c$ that those two; i.e., the circle with center $c$ and radius $cp$ passes through $p$ and $q$, and all other points of $P$ are outside it.}

For any two finite and nonempty sets $S$ and $T$ of points in the plane, the {\it distance}. between them is the minimum of $\dist(s, t)$ for $s\in S$ and $t\in T$. A {\it closest $S$--$T$ pair} is a pair $s$, $t$ that realizes this minimum distance. The following is a useful fact about such pairs:

\theorem{2}{Any closest $S$--$T$ pair is an edge of the Delaunay triangulation.}

\mfig4cm
\proof{Let $s\in S$ and $t\in T$ be a closest $S$--$T$ pair. By definition, the circle $C
s$ with center $s$ and radius $st$ must not contain any point of $T$; and, similarly, the circle $C
t$ with center $t$ and radius $ts$ contains no point of $S$. Therefore, the ``lune'' $C
t\inte C
s$ contains no pont of $S\un T$. We conclude that the circle $C
{st}$ with diameter $st$ passes through $s$ and $t$, and all other points of $S\un T$ are outside it, i.e. that $st$ is an edge of the Delaunay triangulation of $S\un T$.}
\endmfig

By using any of the asymptotically optimal algorithms in the literature [?, \GuiSto?], we can construct the Delaunay triangulation of $S\un T$ in $O(n\log n)$ time, where $n=\leftv S\rightv+\leftv T\rightv$. Since the Delaunay diagram has $O(n)$ edges, by a simply enumerating them we can find a closest $S$--$T$ pair (indeed, all of them) in $O(n\log n)$ total time.

Given any graph whose vertices are points of the plane, we define the {\it length} of any of its edges as the Euclidean distance between its two endpoints. A {it minimal Euclidean spanning tree} (MEST) for a set $P$ of points of $n$ in the plane is defined as a tree having those points for vertices and whose total edge cost is minimum. Such a tree can be constructed by applying any general-purpose minimum spanning tree algorithm [\Prim? \Dijk? \Krus?] to the complete graph with vertex set $P$. However, since this graph has $O(n^2)$ edges, these algorithms would take at least $O(n^2)$.

A well-known property of minimum spanning trees in general is the following:

\lemma{3}{Let $e$ be any edge of a minimum spanning tree $\Tscr$ of a graph $\Gscr$, and $S$, $T$ be the vertex sets of the two components of $\Tscr-e$. Then, among all edges of $\Gscr$ connecting $S$ to $T$, $e$ has minimum cost.}

This property has an important consequence:

\theorem{4}{Any MEST for a point set $P$ is a spanning tree of the Delaunay triangulation of $P$.}
\proof{By lemma 3, every edge $e$ of a MEST for $P$ is a minimum-cost $S$--$T$ edge of the complete graph with vertices $P$ (that is to say, the endpoints of $e$ are a closest $S$--$T$ pair), for some partition $P=S\un T$. By theorem 2, all such edges are edges of the Delaunay triangulation of $P$, hence the result follows.}

Therefore, a MEST for a point set $P$ can be constructed in $O(n\log n)$ time, by first constructing the Delaunay triangulation of $P$ and then applying Prim's (Kruskal's?) algorithm to it.